LeetCode 724. Find Pivot Index / 1991. Find the Middle Index in Array

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

Example 1:

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

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

---

这道题要求一个数组里的一个index，在这个index左边的所有数字之和，和在这个index右边的所有数字之和，是一样的。如果在最左边和最右边的话当0看。刚开始还没理解到最后这句边界条件的意义，后来才发现有可能nums[1]到nums[length - 1]之和为0，这就是corner case。

提到求和就自然地想到了prefix sum的思想，先遍历一遍数组求prefix sum，然后再遍历一遍看看对i来说，左边之和也就是sums[i - 1]，和右边之和也就是sums[length - 1] - sums[i]是否相等，相等就返回就好了。唯一一点就是corner case，因为第二遍遍历数组的时候没有遍历i == 0的情况，需要拎出来单独讨论。也有想过要不要把sums数组增加一个长度，把最左边的sum记为0，但觉得有点绕就还是算了。

class Solution {
    public int pivotIndex(int[] nums) {
        int[] sums = new int[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
        if (sums[nums.length - 1] - sums[0] == 0) {
            return 0;
        }
        for (int i = 1; i < nums.length; i++) {
            if (sums[i - 1] == sums[nums.length - 1] - sums[i]) {
                return i;
            }
        }
        return -1;
    }
}

然后看了solutions居然有O(1) space的做法，根本不需要用到prefix sum数组。其实也是借鉴了prefix sum的思想，记录总和和左边的和就够了。遍历的时候就看左边的和是不是总和减掉它自己的一半。

class Solution {
    public int pivotIndex(int[] nums) {
        int total = 0;
        int left = 0;
        for (int num : nums) {
            total += num;
        }
        for (int i = 0; i < nums.length; i++) {
            if (2 * left == total - nums[i]) {
                return i;
            }
            left += nums[i];
        }
        return -1;
    }
}