FindPivotIndex [source code]

public class FindPivotIndex {
static
/******************************************************************************/
class Solution {
    public int pivotIndex(int[] nums) {
        if (nums.length == 0)
            return -1;
        int leftSum = 0, rightSum = 0;
        for (int num : nums)
            rightSum += num;
        for (int i = 0; i < nums.length; i++) {
            rightSum -= nums[i];
            if (leftSum == rightSum)
                return i;
            leftSum += nums[i];
        }
        return -1;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindPivotIndex.Solution tester = new FindPivotIndex.Solution();
        int[][] inputs = {
            {1, 7, 3, 6, 5, 6}, {3},
            {1, 2, 3}, {-1},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int ans = inputs[2 * i + 1][0];
            System.out.println (Printer.separator ());
            int output = tester.pivotIndex (nums);
            System.out.printf ("%s -> %s, expected: %d\n",
                Printer.array (nums), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

这个题目刚拿到手的时候, 感觉是不是用2pointers来做, 后来想了一下, 这个做法在有tie的情况下不太好处理; 不过后来大概理解了这个题目的意思, 这个题目其实就是希望你用一个类似sliding window的方式来处理;

实际写算法的时候, 类似之前NLP学forward-backward算法的时候一样, 一定要注意好, 对于你使用的变量的准确定义; 比如这里的 leftSum是否包含[i]? rightSum是否包含[i]; 后来想了一下, 这个问题其实没有这个复杂性, 因为这里要你找的其实是不包含[i]的pivot; 所以左右两边都不包含就行了;

最后算是比较轻松愉快的秒杀掉了, 速度是40ms (40%), 我这个算法按理来说应该很优化了, 不过速度反而不是特别好, 看来应该有更好的办法, 估计是可以1pass就做掉;

注意我body里面对于left和right的更新位置的区别处理, 这个是在debug的时候调试想到的;

editorial:

```javaclass Solution { public int pivotIndex(int[] nums) {
int sum = 0, leftsum = 0;
for (int x: nums) sum += x;
for (int i = 0; i < nums.length; ++i) {
if (leftsum == sum - leftsum - nums[i]) return i;
leftsum += nums[i];
}
return -1;
}
}

这题确实没有必要用sliding window的思路来做, 直接维护这样两个sum其实也是可以的, 本质是类似的;  


---

discussion没有什么更新鲜的解法;  


---

submission基本也就是波动;   


---
### Problem Description
Given an array of integers nums, write a method that returns the "pivot" index of this array.  

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.  

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.  

Example 1:

Input:
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

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

Note:

• The length of nums will be in the range [0, 10000].
• Each element nums[i] will be an integer in the range [-1000, 1000].

Difficulty:Easy
Total Accepted:10.2K
Total Submissions:25.2K
Contributor:fishercoder
Companies
coupangradius
Related Topics
array
Similar Questions

Hint 1
We can precompute prefix sums P[i] = nums[0] + nums[1] + ... + nums[i-1]. Then for each index, the left sum is P[i], and the right sum is P[P.length - 1] - P[i] - nums[i].