LeetCode 724. 寻找数组的中心下标
题目描述
题意分析
找到左侧元素和与右侧元素和相等的最左下标，当前元素不计入任何一边。中心下标不一定在数组中间，两端也可能满足条件；不存在元素的一侧，其和视为 0。没有合法下标时返回
-1。
解法：先算总和再左右累计
核心思路
[!blue]
对任意下标
i，数组总和可以拆成三部分：total = 左侧和 + nums[i] + 右侧和。因此只要知道总和与左侧和，就能用total-leftSum-nums[i]得到右侧和，不必为每个下标重新遍历两侧。先遍历一次得到
total，再从左向右检查候选下标。每轮开始时，leftSum恰好是nums[0..i-1]的和：在i=0时它为 0，检查结束后加上nums[i]，就成为下一轮需要的左侧和。在这个状态下比较
leftSum == total-leftSum-nums[i]，正好对应题目的左右和相等条件。检查顺序按下标递增，所以第一次相等即可返回，既不会漏掉候选，也保证结果最靠左。
解题步骤
- 遍历数组求出
total，初始化leftSum = 0。- 从下标 0 开始，比较
leftSum与total-leftSum-nums[i]。- 相等时返回
i；否则执行leftSum += nums[i]，继续检查下一项。- 所有下标都不满足条件时返回
-1。只有一个元素时，两侧都为空，直接返回 0；全为 0 时，所有下标都合法，同样首先返回 0。负数不会影响总和拆分关系，仍按同一公式逐项检查。
代码实现
class Solution {
// 直接算左右和容易重复，先求总和后按下标动态维护左侧和，右侧和可 O(1) 得出。
public int pivotIndex(int[] nums) {
int total = 0;
for (int num : nums) {
total += num;
}
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
// 比较时两侧都不含当前元素，未命中后才累加到左侧
if (leftSum == total - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}
}
func pivotIndex(nums []int) int {
// 直接算左右和容易重复，先求总和后按下标动态维护左侧和，右侧和可 O(1) 得出。
total := 0
for _, num := range nums {
total += num
}
leftSum := 0
for i, num := range nums {
// 比较时两侧都不含当前元素，未命中后才累加到左侧
if leftSum == total-leftSum-num {
return i
}
leftSum += num
}
return -1
}
复杂度分析
- 时间复杂度：$O(n)$，求和与检查各一次。
- 空间复杂度：$O(1)$，两个和与游标。
关键点总结
[!green]
- 当前元素是分割点，两侧都不包含它。
- 含负数时不能根据和的大小决定跳过哪边。
易错点总结
[!yellow]
- 比较之前就加入当前值，会让两侧计算错位。
- 忽略端点，会漏掉空侧和为零的合法情况。
- 找到后继续覆盖答案，会返回最后一个而非最左下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1732. 找到最高海拔 | 简单 | 同样滚动维护前缀和，原题取累计值最大值，本题结合总和计算右侧和。 |
| 238. 除了自身以外数组的乘积 | 中等 | 同样把当前位置两侧拆成前缀与后缀，本题使用和，原题使用乘积且排除自身。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！