LeetCode LCR 012. 寻找数组的中心下标
目录
题目描述
题意分析
给一个整数数组
nums，找出中心下标——它左侧所有元素之和等于右侧所有元素之和；如果有多个，返回最靠左的那个；如果不存在，返回 $-1$。定义里有两处容易读错。其一，中心下标处的元素本身既不算左侧也不算右侧，它是被跳过的。其二，当下标是 $0$ 时左侧为空，空数组的和按 $0$ 处理；下标是 $n-1$ 时右侧同理。这两条决定了实现必须能自然表达「空侧和为零」，而不是靠特判凑出来。
「返回最靠左的那个」意味着一旦命中就可以立即返回，不需要遍历完再挑；同时也说明必须按下标从小到大检查。
数据规模 $n \le 10^4$，$O(n^2)$ 勉强能过但没有必要；每个下标的判定其实只依赖「左侧和」和「右侧和」两个量，而它们在下标推进时都只变化一个元素，这就是把复杂度降到 $O(n)$ 的信号。
元素可以为负、可以为零，所以不能假设前缀和单调，也不能用二分之类依赖单调性的手段；不过本题只是逐个检查，负数并不构成障碍。元素范围 $[-1000, 1000]$、长度 $10^4$，总和绝对值上界 $10^7$，
int足够。
解法：前缀和维护区间信息
核心思路
暴力做法是对每个候选下标
i，分别把左侧和右侧重新加一遍再比较，$O(n^2)$。瓶颈显而易见：相邻的两个候选下标，它们的左右两侧几乎完全重合，却被从头重算了。观察：设
left是nums[0..i-1]的和、right是nums[i+1..n-1]的和。当下标从i推进到i + 1时，left只需加上nums[i]，right只需减去nums[i+1]。也就是说两个量都可以增量维护，每步只做一次加法和一次减法。于是不需要真的开一个前缀和数组：用两个滚动变量就够了。要维护的不变量是：在检查下标
i时，left恰好等于nums[0..i-1]之和，right恰好等于nums[i+1..n-1]之和。为了让这条不变量在每一轮开始时都成立，代码里的三步顺序必须是——先从right里扣掉nums[i]（把当前元素从右侧移出去），再比较left == right，最后把nums[i]累进left（为下一轮做准备）。初值也由不变量倒推：检查
i = 0时左侧为空，所以left初始化为 $0$；右侧是nums[1..n-1]，所以right应先被初始化成整个数组的和，然后在循环第一步扣掉nums[0]，正好得到nums[1..n-1]。这样「空侧和为零」和「首尾下标」都被主逻辑吸收，不需要任何特判。命中即返回，天然满足「最靠左」的要求；循环走完仍未命中就返回 $-1$。
解题步骤
- 先求出整个数组的总和存入
right。这一遍扫描是必需的：要知道「右侧和」，就得先知道「全部的和」。left初始化为 $0$，代表下标 $0$ 左侧的空区间。空区间的和是 $0$，这是数学定义而非约定俗成的特例。- 按下标从小到大遍历，因为题目要最靠左的答案，命中即可
return。- 第一步
right -= nums[i]。把当前元素从右侧移出，这样right的语义才是「严格在i右边的元素之和」，与题意的「不含自身」一致。这一步必须在比较之前。- 第二步比较
left == right，成立就返回i。此刻left是nums[0..i-1]的和（尚未把nums[i]加进去），right是nums[i+1..n-1]的和，两侧都不含nums[i]。- 第三步
left += nums[i]。把当前元素并入左侧，为下一轮维持不变量。这一步必须在比较之后，否则当前元素会被算进左侧。- 循环结束返回 $-1$，表示不存在中心下标。
以
nums = [1, 7, 3, 6, 5, 6]走一遍，期望答案3。预处理：right = 1 + 7 + 3 + 6 + 5 + 6 = 28，left = 0。i = 0：right = 28 - 1 = 27，比较0 == 27不成立，left = 0 + 1 = 1。i = 1：right = 27 - 7 = 20，比较1 == 20不成立，left = 1 + 7 = 8。i = 2：right = 20 - 3 = 17，比较8 == 17不成立，left = 8 + 3 = 11。i = 3：right = 17 - 6 = 11，比较11 == 11成立，返回3——此时左侧是[1, 7, 3]和为 $11$，右侧是[5, 6]和为 $11$，中间的nums[3] = 6两边都不算，完全符合定义。如果把「先扣右侧」和「后加左侧」这两步的顺序对调，i = 3时left会变成 $17$、right变成 $11$，这个正确答案就被漏掉了。
代码实现
class Solution {
public int pivotIndex(int[] nums) {
int left = 0, right = 0;
// right 先装下全部元素的和。
for (int x : nums) {
right += x;
}
int n = nums.length;
for (int i = 0; i < n; ++i) {
// 先把当前元素从右侧移出，使两侧都不含 nums[i]。
right -= nums[i];
if (left == right) {
return i;
}
// 比较之后才并入左侧，为下一轮维持不变量。
left += nums[i];
}
return -1;
}
}
func pivotIndex(nums []int) int {
left, right := 0, 0
for _, x := range nums {
right += x
}
for i, x := range nums {
right -= x
if left == right {
return i
}
left += x
}
return -1
}
复杂度分析
- 时间复杂度：$O(n)$。第一遍求总和扫一次，第二遍逐位判定再扫一次，每个位置只做常数次加减和一次比较。凭的是把「重新累加两侧」换成了「增量地挪动一个元素」。
- 空间复杂度：$O(1)$。只用了
left、right、i三个标量。这里刻意没有开前缀和数组——本题的判定只需要「左侧和」与「右侧和」两个滚动值，把它们物化成数组反而多花 $O(n)$ 空间。
关键点总结
- 「左右两侧某个聚合量相等 / 满足某关系」的题，通用解法就是一次预处理求出全局量，再用两个滚动变量在遍历中做增量维护，$O(n)$ 时间 $O(1)$ 空间。
- 前缀和不一定要落成数组。当每个位置的判定只用到「到此为止的和」与「总和减去它」时，两个标量就够了——能省下数组就省。
- 顺序即语义：先扣右、后加左，中间夹判断，这个三段式精确表达了「当前元素两侧都不算」。写这类代码时应当先把不变量写出来，再倒推三步的先后。
- 「空区间的和是 $0$」不是特例而是定义，让
left从 $0$ 起步就能免掉首尾下标的特判——好的初值设计能吸收掉边界分支。- 面试视角：这题本身不难，面试官真正在看两点——你会不会写出 $O(n^2)$ 的重复累加，以及你能不能一次说清「中心元素自己不参与比较」和「两端空侧按 $0$ 算」。答完主逻辑后主动补一句「
i = 0和i = n-1不需要特判，因为空侧和天然是 $0$」，通常就能收尾；若被追问「元素含负数会不会影响」，回答是不会——本题是逐位判定，没有用到任何单调性。
易错点总结
- 错误写法：把
left += nums[i]写在比较之前。输入[1, 7, 3, 6, 5, 6]时i = 3处left变成 $17$、right是 $11$，正确答案3被漏掉，最终返回-1。- 错误写法：把
right -= nums[i]写在比较之后。当前元素仍留在右侧，输入[1, 7, 3, 6, 5, 6]时i = 3的right是 $17$，同样漏解返回-1。- 错误写法：判定写成
left == right - nums[i]却又保留了right -= nums[i]。当前元素被扣了两次，输入[1, 2, 3]会在i = 1处误判命中，返回1，而正确答案是-1。- 错误写法：
right初始化为 $0$ 而不是总和。所有比较都在拿部分和跟负的部分和比，输入[1, 7, 3, 6, 5, 6]会返回-1。- 错误写法：
left初始化为nums[0]。下标 $0$ 的左侧本应为空，这样写等于把自己算进了左侧，输入[5, 0]（正确答案0）会漏掉解，返回-1。- 错误写法：先收集所有满足条件的下标再返回最小值。逻辑对但多扫一遍且多占空间；更常见的连带错误是排序后返回，输入含多个中心下标时若忘记排序会返回非最左的那个。
- 错误写法：对每个
i用两个内层循环重新累加左右两侧。输入规模 $10^4$ 时是 $10^8$ 级操作，容易卡时限，而且两侧的边界（是否含i）在两处各写一遍，更容易写错。- 错误写法：不存在时返回
0。$0$ 本身是一个合法下标，输入[1, 2, 3]的正确答案是-1，返回0会被判成「下标 0 是中心」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 724. 寻找数组的中心下标 | 简单 | 与本题同题，可直接套用同一份三段式循环 |
| 1480. 一维数组的动态和 | 简单 | 只要求输出前缀和序列，是本题预处理步骤的最小形态 |
| 1732. 找到最高海拔 | 简单 | 在前缀和推进过程中取最大值，同样只需一个滚动变量 |
| 303. 区域和检索 - 数组不可变 | 简单 | 需要多次任意区间查询，此时必须把前缀和物化成数组而非滚动变量 |
| 238. 除了自身以外数组的乘积 | 中等 | 同样是「左侧聚合 × 右侧聚合」，但禁用除法，需两趟前后缀相乘 |