§1
题目描述
给你一个整数数组 nums,请计算数组的中心下标。中心下标是数组中的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端,则左侧数之和视为 0;位于最右端,则右侧数之和视为 0。返回最靠左的中心下标;如果不存在,返回 -1。
输入 = nums = [1,7,3,6,5,6]
输出 = 3
解释 = 下标 3 左侧和 1+7+3=11,右侧和 5+6=11。
输入 = nums = [1,2,3]
输出 = -1
§2
思路解析动画文字版
如果每个位置都重新求和,复杂度会到 O(n^2)。这题可以用一次总和和一个滚动 left 解决。
循环不变量是:检查下标 i 之前,left 永远只包含 i 左侧的元素,不包含 nums[i] 本身。
初始化:total=28,left=0:left 从 0 开始,因为还没站到任何下标,左侧没有元素。
i=0:计算右侧和:站在下标 0,左侧和是 0,右侧和是 7+3+6+5+6=27,不相等。
i=0 不满足:把 nums[0] 加进 left:离开下标 0 后,nums[0] 就会成为下一个位置的左侧元素。
i=1:计算右侧和:下标 1 左侧只有 [1],left=1;右侧是 [3,6,5,6],right=20,不相等。
i=1 不满足:更新 left:现在 left=1+7=8,代表下标 2 左侧的元素和。
i=2:计算右侧和:下标 2 左侧和是 8,右侧和是 17,仍然不是中心下标。
i=2 不满足:更新 left:更新后 left=11,也就是 [1,7,3] 的和。
i=3:left 和 right 相等:下标 3 左侧和 11,右侧和 11,第一次相等,所以直接返回 3。
返回最靠左的中心下标:因为从左到右扫描,第一次命中的下标天然就是最靠左的中心下标。
顺序不能反:如果先 left += nums[i],left 就把当前元素也算进去了。
§3
参考代码
class Solution: def pivotIndex(self, nums): total = sum(nums) left = 0 for i, x in enumerate(nums): right = total - left - x if left == right: return i left += x return -1看懂代码不等于写得出。盖住上面,自己默写一遍试试。卡在哪一行说不清,就点右下角问小欧。
§4
复杂度
- 时间复杂度:O(n),sum(nums) 扫一次,for 循环再扫一次。
- 空间复杂度:O(1),只维护 total、left、right 等常数变量。
§5
易错点
✗ 错误写法:先 left += nums[i] 再判断
✓ 正确写法:先判断 left == right,再更新 left
中心下标左右两侧都不包含 nums[i]。
✗ 错误写法:忘记返回最靠左
✓ 正确写法:从左到右第一次命中就返回
题目要求最靠左的中心下标。
✗ 错误写法:left=0 时以为不合法
✓ 正确写法:最左端左侧和视为 0
题目明确允许边界位置成为中心下标。
✗ 错误写法:遇到负数就放弃前缀思路
✓ 正确写法:负数不影响总和相减
这题只做加减,不依赖单调性。
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
下一题 · 前缀和套路 3/6
→二维区域和检索 - 矩阵不可变
LeetCode 304 · 中等 · 沿着 前缀和套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路?去图解算法专题