Problem

My Solution

python

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if sum(nums[:i]) == sum(nums[i+1:]):
                return i
            
        return -1

• 굉장히 많은 data에서 Time Error ...

cpp

#include <numeric>

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i == 0) {
                sum1 = accumulate(nums.begin() + 1, nums.end(), 0);
                if (!(sum1)) {
                    return 0;
                }
            } else {
                sum1 = accumulate(nums.begin(), nums.begin() + i, 0);
                sum2 = accumulate(nums.begin() + i + 1, nums.end(), 0);
                
                if (sum1 == sum2) {
                    return i;
                }
            }
        }
             
        return -1;
    }
};

Reference Solution

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        S = sum(nums)
        leftsum = 0
        for i, x in enumerate(nums):
            if leftsum == (S - leftsum - x):
                return i
            leftsum += x
        return -1

• Time Complexity: O(N), where N is the length of nums.
• Space Complexity: O(1), the space used by leftsum and S.
• 이렇게도 할 수 있구나 ..

S - nums[i] - leftsum.