724. 寻找数组的中心下标
题目描述
输入整数数组 nums。若某个下标 i 左边所有元素的和等于右边所有元素的和（都不算 nums[i] 本身），称 i 为中心下标。
某一侧没有元素时，那一侧的和按 0 计算，所以下标 0 和最后一个下标也可能是中心下标。
下标从 0 开始。返回最小的中心下标；若不存在，返回 -1。
示例 1
输入：nums = [1,7,3,6,5,6] 输出：3
解释：下标 3 左边和为 1+7+3=11，右边和为 5+6=11。
示例 2
输入：nums = [1,2,3] 输出：-1
解释：没有任何下标满足两侧和相等。
示例 3
输入：nums = [2,1,-1] 输出：0
解释：下标 0 左边和为 0，右边和为 1+(-1)=0。
数据范围
1 <= nums.length <= 10^4-1000 <= nums[i] <= 1000
解题思路
先求总和 total。从左往右扫描，维护左侧和 left，则右侧和 = total - left - nums[i]。左右相等即 left == total - left - nums[i]，也就是 2*left + nums[i] == total。不满足就把 nums[i] 加进 left 继续。
为什么正确
检查下标 i 时，left 恰好等于 nums[0..i-1] 之和；由于从左往右检查，第一个满足条件的下标就是最靠左的答案。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
数组里可能有负数，不能在左侧和超过一半时提前停止；右侧和不包含 nums[i] 本身，不要写成 left == total - left。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total = sum(nums)
left = 0
for i, x in enumerate(nums):
if left * 2 + x == total:
return i
left += x
return -1class Solution {
public int pivotIndex(int[] nums) {
int total = 0;
for (int x : nums) total += x;
int left = 0;
for (int i = 0; i < nums.length; i++) {
if (left * 2 + nums[i] == total) {
return i;
}
left += nums[i];
}
return -1;
}
}class Solution {
public:
int pivotIndex(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
int left = 0;
for (int i = 0; i < (int)nums.size(); i++) {
if (left * 2 + nums[i] == total) {
return i;
}
left += nums[i];
}
return -1;
}
};func pivotIndex(nums []int) int {
total := 0
for _, x := range nums {
total += x
}
left := 0
for i, x := range nums {
if left*2+x == total {
return i
}
left += x
}
return -1
}var pivotIndex = function(nums) {
const total = nums.reduce((s, x) => s + x, 0);
let left = 0;
for (let i = 0; i < nums.length; i++) {
if (left * 2 + nums[i] === total) {
return i;
}
left += nums[i];
}
return -1;
};function pivotIndex(nums: number[]): number {
const total = nums.reduce((s, x) => s + x, 0);
let left = 0;
for (let i = 0; i < nums.length; i++) {
if (left * 2 + nums[i] === total) {
return i;
}
left += nums[i];
}
return -1;
}