剑指 Offer II 012. 左右两边子数组的和相等

前缀和

class Solution {
    public int pivotIndex(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int len = nums.length;
        // get prefix sum
        int[] sum = new int[len];
        sum[0] = nums[0];
        for (int i = 1; i < len; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        // caculate pivote index
        for (int i = 0; i < len; i++) {
            int leftSum = i == 0 ? 0 : sum[i - 1];
            int rightSum = i == len - 1 ? 0 : sum[len - 1] - sum[i];
            if (leftSum == rightSum) return i;
        }
        return -1;
    }
}

数组总和

不需要计算每个元素的前缀和（即不需要计算得到前缀和数组），而是先遍历一遍数组得到总和 total，然后再次遍历数组，得到区间 [0, i] 的前缀和，那么左边就是 sum - nums[i]，右边总和就是 total - sum

class Solution {
    public int pivotIndex(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int len = nums.length;
        // get prefix sum
        int total = 0;
        for (int i = 0; i < len; i++) {
            total += nums[i];
        }
        // caculate pivote index
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            int leftSum = sum - nums[i];
            int rightSum = total - sum;
            if (leftSum == rightSum) return i;
        }
        return -1;
    }
}