题目描述
思路解析动画文字版
两个关键量:total 是固定的总和,leftSum 是边走边攒的左边和。右边和 = total − leftSum − 当前值,一减就有,省去重复累加。
第一步:先把整个数组加一遍,得到总和 total = 7。后面每个位置的右边和都靠它减出来,不用再重复加。
leftSum 记「当前位置左边的和」,一开始是 0(下标 0 左边什么都没有)。指针 i 从最左边开始检查。
指针 i 到下标 0(高亮的是它左边那段)。左边和是 0;右边和不用重加,用 total 7 减去左边和 0 再减去自己 3,得 4。
左边和 0 和右边和 4 不相等,下标 0 不是中心下标(标红)。把当前值 3 累加进 leftSum,再去看下一个位置。
指针 i 到下标 1(高亮的是它左边那段)。左边和是 3;右边和不用重加,用 total 7 减去左边和 3 再减去自己 -2,得 6。
左边和 3 和右边和 6 不相等,下标 1 不是中心下标(标红)。把当前值 -2 累加进 leftSum,再去看下一个位置。
指针 i 到下标 2(高亮的是它左边那段)。左边和是 1;右边和不用重加,用 total 7 减去左边和 1 再减去自己 1,得 5。
左边和 1 和右边和 5 不相等,下标 2 不是中心下标(标红)。把当前值 1 累加进 leftSum,再去看下一个位置。
指针 i 到下标 3(高亮的是它左边那段)。左边和是 2;右边和不用重加,用 total 7 减去左边和 2 再减去自己 -4,得 9。
左边和 2 和右边和 9 不相等,下标 3 不是中心下标(标红)。把当前值 -4 累加进 leftSum,再去看下一个位置。
指针 i 到下标 4(高亮的是它左边那段)。左边和是 -2;右边和不用重加,用 total 7 减去左边和 -2 再减去自己 2,得 7。
左边和 -2 和右边和 7 不相等,下标 4 不是中心下标(标红)。把当前值 2 累加进 leftSum,再去看下一个位置。
指针 i 到下标 5(高亮的是它左边那段)。左边和是 0;右边和不用重加,用 total 7 减去左边和 0 再减去自己 -1,得 8。
左边和 0 和右边和 8 不相等,下标 5 不是中心下标(标红)。把当前值 -1 累加进 leftSum,再去看下一个位置。
指针 i 到下标 6(高亮的是它左边那段)。左边和是 -1;右边和不用重加,用 total 7 减去左边和 -1 再减去自己 2,得 6。
左边和 -1 和右边和 6 不相等,下标 6 不是中心下标(标红)。把当前值 2 累加进 leftSum,再去看下一个位置。
指针 i 到下标 7(高亮的是它左边那段)。左边和是 1;右边和不用重加,用 total 7 减去左边和 1 再减去自己 -3,得 9。
左边和 1 和右边和 9 不相等,下标 7 不是中心下标(标红)。把当前值 -3 累加进 leftSum,再去看下一个位置。
指针 i 到下标 8(高亮的是它左边那段)。左边和是 -2;右边和不用重加,用 total 7 减去左边和 -2 再减去自己 2,得 7。
左边和 -2 和右边和 7 不相等,下标 8 不是中心下标(标红)。把当前值 2 累加进 leftSum,再去看下一个位置。
指针 i 到下标 9(高亮的是它左边那段)。左边和是 0;右边和不用重加,用 total 7 减去左边和 0 再减去自己 7,得 0。
左边和 0 正好等于右边和 0!下标 9(高亮这一格)就是中心下标。题目要最靠左的,找到第一个就可以直接返回 9。
三个高频追问:总和怎么省掉重复累加、多解取最左、以及两端的空边界算 0。
参考代码
def pivotIndex(nums): total = sum(nums) # 数组总和 left = 0 # 当前位置左边的和 for i, x in enumerate(nums): if left == total - left - x: # 左和 == 右和 return i left += x # 把当前值并入左边 return -1复杂度
- 时间:O(n),求总和扫一遍,再走一遍逐位判断,每位只做常数次加减比较
- 空间:O(1),只用 total 和 left 两个变量,不开额外数组
易错点
面试追问把动画讲成自己的话
追问为什么求一次总和就能避免重复累加右边?
追问如果有多个中心下标怎么办?
追问下标 0 或最后一个下标能当中心下标吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
二维区域和检索 - 矩阵不可变
LeetCode 304 · 中等 · 沿着 前缀和套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题