https://leetcode.com/problems/find-pivot-index/

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

pivot 을 기준으로 왼쪽 전부의 합 과 오른쪽 전부의 합이 같아야 한다.

매 elem 을 돌아가면서 하게되면 O(n^2)이 걸린다.

하나를 지정하고 나머지를 더하고, 다음 elem을 지정하고 나머지를 더하고... 반복하면 오래 걸리니까 다른방법을 찾아보자.

sliding 이라는 개념이 있다고 한다. (positive number일때)

모든 elem의 합을 구하고, (O(n)), 첫번째 를 pivot으로 잡는다.

그리고 pivot의 수를 합에서 빼준다. pivot을 한칸 오른쪽으로 옮긴다.

다시 합에서 pivot의 수를 빼주고, 왼쪽에 이전 pivot의 값을 더해준다.

이걸 반복한다.

class Solution {
public:
	int pivotIndex(vector<int>& nums) {
		int sum = 0;
		int leftSum = 0;
		int pastPivot = 0;
		for (int i = 0; i < nums.size(); ++i)
		{
			sum += nums[i];
		}
		for (int i = 0; i < nums.size(); i++)
		{
			sum -= nums[i];
			leftSum += pastPivot;
			if (sum == leftSum)
				return i;
			pastPivot = nums[i];
		}
		return -1;
	}
};

Runtime: 20 ms, faster than 99.43% of C++ online submissions for Find Pivot Index.

Memory Usage: 30.9 MB, less than 99.67% of C++ online submissions for Find Pivot Index.

O(n) 으로 해결된다.