724. Find Pivot Index

二刷

Version #1 2 Passes

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 78.73% of Java online submissions for Find Pivot Index.

Memory Usage: 51.6 MB, less than 82.34% of Java online submissions for Find Pivot Index.

class Solution {

    public int pivotIndex(int[] nums) {

        int right = 0;

        for (int num : nums) {

            right += num;

        }

        int left = 0;

        for (int i = 0; i < nums.length; i++) {

            right -= nums[i];

            if (left == right) {

                return i;

            }

            left += nums[i];

        }

        return -1;

    }

}

一刷
第一个想法是双指针从左右分别扫，谁的sum小就多移动一个
但是对于负数的case 是不成立的
看的答案，改成先求sum，然后从左扫到右

bug

Input:[-1,-1,-1,0,1,1]

Output:-1

Expected:0

 0 也能算是pivot...

47.09 %
class Solution {
    public int pivotIndex(int[] nums) {
        if (nums == null) {
            return -1;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftSum == sum - nums[i] - leftSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}