Leetcode - 724. Find Pivot Index

문제

특정 index를 기준으로 좌/우 배열값의 합이 동일한 index를 리턴하라.

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

해결 O(N)

brute force로 한다면 (n^2)이 되겠지만. Prefix Sum(구간합 테그닉?)을 사용하면 O(n)에 해결이 가능.
처음에 l_sum/r_sum을 먼저 구해놓고.
배열을 하나씩 순회하면서 아래와같이 현재 index값을 빼거나 더하는 방식으로 l_sum/r_sum을 O(1)에 계산.

• l_sum = l_sum + nums[i - 1]
• r_sum = r_sum - nums[i]

int pivotIndex(int* nums, int numsSize){
    int l_sum = 0;
    int r_sum = 0;
    int pivot = -1;
    for (int i = 1; i < numsSize; i++)
        r_sum += nums[i];
    if (l_sum == r_sum)
        return 0;
    for (int i = 1; i < numsSize; i++) {
        l_sum = l_sum + nums[i - 1];
        r_sum = r_sum - nums[i];
        if (l_sum == r_sum) {
            pivot = i;
            break;
        }
    }
    return pivot;
}