LeetCode LCR 012. 寻找数组的中心下标
题目描述
题意分析
找到一个下标，使它严格左侧的元素和等于严格右侧的元素和，当前下标对应的元素不计入任意一边。若有多个答案，返回最靠左的下标；没有则返回
-1。首尾位置也可以是答案，不存在元素的一侧按和为零处理。数组可以包含负数和零，中心下标并不一定在数组中间，也不要求左右元素数量相同。
解法：左右和同步扫描
核心思路
[!blue]
相邻候选下标的左右区域高度重合，没有必要对每个位置重新求和。先把总和放入
right，令left = 0，再按下标从小到大移动分界。开始处理当前位置
i时，left已经是它严格左侧的和，而right还包含当前位置及其右侧。先从right减去nums[i]，当前元素就被两侧同时排除，此时比较left == right恰好对应题目定义。如果不相等，再把
nums[i]加入left，为下一位置准备好左侧和。顺序固定为“先扣右侧、再比较、后加左侧”，使两个滚动变量始终具有清楚的范围含义。第一轮左侧自然为空，最后一轮扣掉末项后右侧自然为空，不需要额外特判。从左向右首次命中就返回，也自然保证最靠左。负数只影响和的值，不影响这种精确加减，因为这里没有依赖任何单调性。
解题步骤
- 将
left初始化为零，遍历数组把全部元素累加到right。- 按下标从小到大处理，先执行
right -= nums[i]。- 两侧和相等时返回当前下标。
- 否则执行
left += nums[i]，继续下一位置。- 全部位置都不满足时返回
-1。
代码实现
class Solution {
public int pivotIndex(int[] nums) {
int left = 0;
int 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
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(n)$，求总和与逐项检查各扫描一次。
- 辅助空间复杂度：$O(1)$，只保留左右和及下标，不需要完整前缀数组。
关键点总结
[!green]
- 当前元素不属于任意一侧，更新顺序直接体现这个条件。
- 从左向右首次命中即可满足最左答案要求。
- 空侧和为零使首尾位置统一处理，负数不会破坏计算。
易错点总结
[!yellow]
- 比较前把当前元素加入左和，或比较后才从右和扣除，都会错误包含自身。
- 只检查内部位置，会漏掉合法的首尾下标。
- 命中后继续覆盖答案可能得到较右的位置，应立即返回。
- 零是合法下标，不能把它当作无解标记；无解返回负一。
- 不要把“中心”误解为中点或左右等长，题目只要求两侧元素和相等。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1732. 找到最高海拔 | 简单 | 同样滚动维护前缀和，原题取累计值最大值，本题结合总和计算右侧和。 |
| 238. 除了自身以外数组的乘积 | 中等 | 同样把当前位置两侧拆成前缀与后缀，本题使用和，原题使用乘积且排除自身。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！