LeetCode 724. 寻找数组的中心下标
目录
题目描述
题意分析
找一个下标
i，使得它左边所有元素之和等于它右边所有元素之和（nums[i]自己不算进任何一边）。存在多个时返回最靠左的那个，不存在则返回 -1。要什么：一个下标，而且是最小的那个。所以扫描方向必须是从左到右，且一命中就立刻返回——不能先把所有候选收集起来再取最小，那是白做功。
定义里有两处必须抠死的细节。第一，
nums[i]本身两边都不属于，它是被排除在外的分割点，不是归给某一侧。第二，最左端和最右端也是合法候选：i = 0时左边是空区间，和为 0；i = n - 1时右边是空区间，和同样为 0。空区间的和是 0 而不是「无效」，这一点让端点无需任何特判。约束透露的信号：元素可以是负数，长度上万。允许负数是这道题最重要的信号，它直接封死了所有依赖单调性的做法——前缀和不再随下标递增，双指针无法通过「和太小就右移」来收缩，二分更是无从谈起。剩下能用的只有「一次线性扫描 + 常数状态」这一条路。数据规模只有 $10^4$，$O(n^2)$ 勉强能过，但这题存在的意义就是练前缀和的等式变形，写成平方级等于没做。
边界：数组长度至少为 1；长度为 1 时唯一的下标 0 左右都是空区间，答案恒为 0；总和可能为负；元素值在 $\pm 1000$ 以内、长度 $10^4$，总和最大 $10^7$，
int完全够用，不必上long。
解法：先算总和再左右累计
核心思路
先看暴力：对每个下标
i，分别用一层循环累加左边和右边，比较是否相等。时间 $O(n^2)$。瓶颈在于相邻两个下标的左侧和只差一个元素，却每次都从头重算——i处的左侧和是i-1处的左侧和加上nums[i-1]，这个增量关系被完全浪费了。顺着增量关系走，自然想到边扫边维护
leftSum。但右侧和怎么办？如果也想边扫边维护一个rightSum，就得先知道全部元素之和才能倒推，那还不如直接把这个「全部之和」求出来。于是得到本解法的两趟结构：第一趟只做一件事——求出总和total；第二趟从左到右扫描，用leftSum和total现场算出右侧和。关键恒等式是：把数组按下标
\[\text{rightSum}(i) = \text{total} - \text{leftSum}(i) - nums[i]\]i切成三段，左段、nums[i]、右段，三者之和必然等于total，因此判定条件随之变成一行：
\[\text{leftSum} == \text{total} - \text{leftSum} - nums[i]\]于是右侧和根本不需要单独维护，$O(1)$ 就能从已有的两个量导出。
本解法的循环不变量是：在进入第
i轮循环体的那一刻，leftSum恰好等于nums[0..i-1]的和（i = 0时为空区间，值为 0）。维持这个不变量的手段是「先判定，后累加」：判定用的leftSum必须是不含nums[i]的那个值，判定完成后再执行leftSum += nums[i]，为下一轮做好准备。有了这个不变量，两个端点都自动成立：
i = 0时leftSum = 0正是空左区间的和；i = n - 1时判定式右侧退化成total - leftSum - nums[n-1] = 0，正是空右区间的和。一个特判都不用写。顺带说明为什么等式要写成
leftSum == total - leftSum - nums[i]而不是化简成2 * leftSum + nums[i] == total——两者数学上等价，后者甚至少一次运算；但前者的每一项都有直白的物理含义（左边是左侧和，右边是右侧和），读代码的人一眼就能对上题意，而化简式需要在脑子里再推一次。可读性在面试白板上比省一次减法重要。
解题步骤
- 第一趟遍历累加出
total。为什么必须是独立的一趟：右侧和的计算依赖全局信息，而扫描到i时后面的元素还没被看过；只有先拿到总和，才能在第二趟里用减法反推出右侧和。leftSum初始化为 0。为什么是 0 而不是nums[0]：不变量要求leftSum在第i轮开始时等于前i个元素之和，i = 0时前 0 个元素之和就是 0；写成nums[0]会让下标 0 这个候选被跳过。- 第二趟从
i = 0扫到n - 1，先做判定leftSum == total - leftSum - nums[i]。为什么判定必须排在累加之前：nums[i]不属于左侧，一旦提前累加进leftSum，判定式的两边就都错了——左边多算了nums[i]，右边少减了它。- 命中立刻
return i。为什么可以立刻返回：扫描顺序天然从小到大，第一个满足条件的下标就是最小的那个，继续扫下去只会找到更大的候选。- 未命中则
leftSum += nums[i]，进入下一轮。为什么这样能维持不变量：进入第i+1轮时，leftSum恰好包含了nums[0..i]，正是前i+1个元素之和。- 循环结束返回 -1。为什么不能返回 0 或抛异常：题面明确规定不存在中心下标时返回 -1，而 0 是一个合法下标值，用它表示「不存在」会与真实答案混淆。
以
具体用例 nums = [1, 7, 3, 6, 5, 6]走一遍，预期答案是 3。第一趟：
total = 1 + 7 + 3 + 6 + 5 + 6 = 28。第二趟，
leftSum初始为 0：
i = 0（nums[0] = 1）：左侧和leftSum = 0（空区间），右侧和28 - 0 - 1 = 27，即7+3+6+5+6 = 27，对得上。0 != 27，不命中。累加后leftSum = 1。
i = 1（nums[1] = 7）：左侧和 1，右侧和28 - 1 - 7 = 20，即3+6+5+6 = 20，对得上。1 != 20，不命中。累加后leftSum = 8。
i = 2（nums[2] = 3）：左侧和 8（即1+7），右侧和28 - 8 - 3 = 17，即6+5+6 = 17。8 != 17，不命中。累加后leftSum = 11。
i = 3（nums[3] = 6）：左侧和 11（即1+7+3），右侧和28 - 11 - 6 = 11，即5+6 = 11。两边相等，命中，返回 3。再走一个体现边界的用例
nums = [2, 1, -1]，预期答案是 0。
total = 2 + 1 + (-1) = 2。
i = 0：leftSum = 0，右侧和2 - 0 - 2 = 0，即1 + (-1) = 0。相等，返回 0。这个例子同时展示了两件事：左端点的空区间和 0 是合法的，以及负数让右侧和可以「反向抵消」——任何依赖前缀和单调递增的思路在这里都会失效。最后走一个无解用例
nums = [1, 2, 3]：total = 6。i = 0：0vs6-0-1=5，不等，leftSum = 1。i = 1：1vs6-1-2=3，不等，leftSum = 3。i = 2：3vs6-3-3=0，不等。循环结束，返回 -1。
代码实现
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(n^2)$，省下的正是「相邻下标之间重复累加」的那部分。
- 空间复杂度：$O(1)$。凭什么：只用了
total、leftSum、i三个标量，没有开前缀和数组。虽然这题的思路来自前缀和，但因为只需要「当前位置的前缀和」这一个值，用一个变量滚动即可，不必物化整张前缀和表——这是前缀和类题目里最常见的一次空间优化。
关键点总结
- 「左段 + 当前元素 + 右段 = 总和」是一条可以随手写出的恒等式，它让右侧和不必单独维护。凡是需要同时掌握「某点左右两侧聚合值」的题目，先求全局总量再用减法反推，通常比维护两个方向的累积量更省事也更不易错。
- 循环不变量要精确到「进入循环体那一刻」。这里是「
leftSum等于nums[0..i-1]之和」，它直接决定了累加语句必须放在判定之后。写这类边扫边累的代码时，先在纸上写清不变量，语句顺序就不用猜了。- 让空区间的和等于 0，端点就不需要特判。把「空」定义成加法的单位元，是让主逻辑自然覆盖边界的通用技巧；反之若把端点当成特殊情况单独处理，代码会立刻变长且容易漏。
- 元素可能为负，是排除单调性做法的硬信号。看到「整数」而不是「正整数」时，要主动放弃双指针收缩、前缀和二分这类依赖单调性的思路。
- 求「最左的满足条件者」就用从左到右扫 + 立即返回，不要收集全部候选再取最小；这既省时间，也让「多解时返回哪个」这条要求从代码结构上被保证，而不是靠事后挑选。
- 表达式的可读性优先于省一次运算。
leftSum == total - leftSum - nums[i]比等价的2 * leftSum + nums[i] == total多一次减法，但前者的两边分别就是左侧和与右侧和，白板上讲解时一句话说清；后者要现推。- 面试视角：这题本身不难，面试官真正想看的是你能否把「两侧和相等」这个条件干净地转成一个 $O(1)$ 可判定的等式，以及能否主动说清端点为什么不用特判。常见追问是「如果要返回所有中心下标呢」（去掉提前返回，改为收集到列表）和「如果数组会被频繁修改并多次查询呢」（这时应改用树状数组或线段树维护前缀和，单次修改与查询都是 $O(\log n)$）。能顺势聊到后者，说明你理解前缀和「静态查询快、动态更新慢」的本质局限。
易错点总结
- 错误写法：先
leftSum += nums[i]再做判定 → 用例nums = [1,7,3,6,5,6]，i = 3时leftSum已变成 17，判定式右侧算成28 - 17 - 6 = 5，17 != 5不命中；后续也不会命中，最终返回 -1，而正确答案是 3。- 错误写法：判定式写成
leftSum == total - leftSum（忘了减nums[i]） → 用例nums = [1,7,3,6,5,6]，等价于把nums[i]划归右侧；i = 3时右侧算成 17 而非 11，不命中，整轮扫描无解返回 -1。题面明确规定中心元素两边都不算。- 错误写法：
leftSum初始化为nums[0]→ 用例nums = [2,1,-1]，下标 0 这个正确答案在第一轮就被错误的leftSum = 2挡掉（2vs2-2-2=-2），继续扫描后返回 -1。- 错误写法：循环从
i = 1开始，认为端点不可能是答案 → 用例nums = [1]，唯一合法下标 0 被跳过，返回 -1；正确答案是 0，因为左右都是空区间、和都为 0。- 错误写法：循环到
i < n - 1为止，认为最后一个下标不可能是答案 → 用例nums = [1,-1,0]，total = 0；下标 0 不满足（左 0、右-1+0 = -1），下标 1 不满足（左 1、右 0），下标 2 满足（左1+(-1) = 0、右为空区间和 0），正确答案是 2；不扫到末位就会漏解返回 -1。- 错误写法：找到后不返回而是记录下来继续扫，最后返回最后一次记录的下标 → 用例
nums = [0,0,0]，三个下标全部满足，正确答案是最小的 0，该写法返回 2。- 错误写法：无解时返回 0 → 用例
nums = [1,2,3]，不存在中心下标，返回 0 会被误解成「下标 0 是答案」。哨兵值必须选一个不可能是合法答案的数，这里题面指定为 -1。- 错误写法：用双指针从两端向中间收缩，哪边小就移哪边 → 用例
nums = [2,-1,-1,2]，前缀和随负数上下波动，「和小就右移」的收缩规则不再保证不漏解，指针会停在错误位置。允许负数时任何依赖单调性的收缩都不成立。- 错误写法：预先构造完整的前缀和数组
pre[i+1] = pre[i] + nums[i]，再用pre[i]与pre[n] - pre[i+1]比较，但下标写成pre[n] - pre[i]→ 用例nums = [1,7,3,6,5,6]，pre[n] - pre[i]包含了nums[i]自己，右侧和被高估，i = 3处算成 17 而非 11，漏掉正确答案。用前缀和数组时，右侧和必须从i + 1开始取。- 错误写法：把
total与leftSum声明为long之后返回类型也顺手改动，或反过来担心溢出而全程用long→ 本题元素绝对值不超过 1000、长度不超过 $10^4$，总和上界 $10^7$，int绰绰有余；无谓的类型放大不会出错但会掩盖你对数据范围的判断，面试中被问到「为什么用 long」却答不出具体上界是减分项。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 012. 寻找数组的中心下标 | 简单 | 与本题同题，可直接套用同一份代码 |
| 303. 区域和检索 - 数组不可变 | 简单 | 需要多次任意区间查询，必须真的把前缀和数组物化下来而非用单个变量滚动 |
| 238. 除了自身以外数组的乘积 | 中等 | 把加法换成乘法且禁用除法，只能左右各扫一遍累积，无法用「总积除以自身」反推 |
| 560. 和为 K 的子数组 | 中等 | 前缀和配哈希表统计出现次数，求的是子数组个数而非分割点，含负数时不能用滑窗 |
| 974. 和可被 K 整除的子数组 | 中等 | 前缀和取模后按同余类计数，难点在负数取模要归一化到非负 |
| 1013. 将数组分成和相等的三个部分 | 简单 | 从一个分割点变成两个，需先判断总和能否被 3 整除，再贪心地找前两段边界 |
| 1732. 找到最高海拔 | 简单 | 前缀和的最基础形态，边累加边取最大值，起点 0 必须计入候选 |
| 1685. 有序数组中差绝对值之和 | 中等 | 同样靠「总和减左侧和」拆解每个位置的贡献，但要利用有序性去掉绝对值符号 |