724. Find Pivot Index

前缀和 O(n) time O(1) space

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        int presum = 0;
        for (int i = 0; i < n; ++i) {
            if (presum == sum - presum - nums[i]) {
                return i;
            }
            presum += nums[i];
        }
        return -1;
    }
};

前缀和 O(n) time O(n) space

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