Poison

724. Find Pivot Index

发表于
Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int pivotIndex(int[] nums) {
        int[] prefixSumArray = new int[nums.length]; // 前缀和数组，不包含当前元素
        int[] suffixSumArray = new int[nums.length]; // 后缀和数组，不包含当前元素

        for (int i = 1; i < nums.length; i++) {
            prefixSumArray[i] = prefixSumArray[i - 1] + nums[i - 1];
            suffixSumArray[nums.length - i - 1] = suffixSumArray[nums.length - i] + nums[nums.length - i];
        }

        for (int i = 0; i < nums.length; i++) {
            if (prefixSumArray[i] == suffixSumArray[i]) {
                return i;
            }
        }

        return -1;
    }
}
Prefix Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int pivotIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int prefixSum = 0; // 前缀和，不包括当前元素
        for (int i = 0; i < nums.length; i++) {
            if (totalSum - (prefixSum + nums[i]) == prefixSum) {
                return i;
            }
            prefixSum += nums[i];
        }

        return -1;
    }
}
Reference

724. Find Pivot Index
1991. Find the Middle Index in Array
剑指 Offer II 012. 左右两边子数组的和相等