题目描述
思路解析动画文字版
记牢一句:ans[i] = ans[i-1] + nums[i],第 0 位就是 nums[0]。一个累加器从左滚到右,扫一遍全部前缀和都出来。下面每帧都在套这句。
总览 · 源数组 + 空的动态和：先看清画面。上面是源数组 nums = [2,4,1,3,2,5,1,4,2,3],一共 10 个数。右边那张表是要填的动态和 ans,现在还是空的。我们准备一个累加器,起始值是 0,然后让紫色指针从下标 0 开始一格一格往右走,每走一格就把当前数加进累加器,得到的就是这一格的前缀和,记进右边的表。先从第 0 位开始。
第 0 位 · 读 nums[0] = 2：从第 0 位开始。紫色指针落在源数组下标 0,值是 2。它前面没有任何数,所以这一格的动态和起点就是它自己,累加器此刻是 0,等会儿 0 加上 2 就是 ans[0]。
第 0 位 · 写入 2：把 0 加上 2 得到 2,写进动态和的第 0 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2]。这个 2 又会成为下一格的累加器 prev,继续往右滚。
第 1 位 · 读 nums[1] = 4：轮到第 1 位。紫色指针落在源数组下标 1,值是 4。右边表里上一格 ans[0] 已经是 2,它就是前 1 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 4。
第 1 位 · 写入 6：把 2 加上 4 得到 6,写进动态和的第 1 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6]。这个 6 又会成为下一格的累加器 prev,继续往右滚。
第 2 位 · 读 nums[2] = 1：轮到第 2 位。紫色指针落在源数组下标 2,值是 1。右边表里上一格 ans[1] 已经是 6,它就是前 2 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 1。
第 2 位 · 写入 7：把 6 加上 1 得到 7,写进动态和的第 2 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7]。这个 7 又会成为下一格的累加器 prev,继续往右滚。
第 3 位 · 读 nums[3] = 3：轮到第 3 位。紫色指针落在源数组下标 3,值是 3。右边表里上一格 ans[2] 已经是 7,它就是前 3 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 3。
第 3 位 · 写入 10：把 7 加上 3 得到 10,写进动态和的第 3 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10]。这个 10 又会成为下一格的累加器 prev,继续往右滚。
第 4 位 · 读 nums[4] = 2：轮到第 4 位。紫色指针落在源数组下标 4,值是 2。右边表里上一格 ans[3] 已经是 10,它就是前 4 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 2。
第 4 位 · 写入 12：把 10 加上 2 得到 12,写进动态和的第 4 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12]。这个 12 又会成为下一格的累加器 prev,继续往右滚。
第 5 位 · 读 nums[5] = 5：轮到第 5 位。紫色指针落在源数组下标 5,值是 5。右边表里上一格 ans[4] 已经是 12,它就是前 5 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 5。
第 5 位 · 写入 17：把 12 加上 5 得到 17,写进动态和的第 5 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17]。这个 17 又会成为下一格的累加器 prev,继续往右滚。
第 6 位 · 读 nums[6] = 1：轮到第 6 位。紫色指针落在源数组下标 6,值是 1。右边表里上一格 ans[5] 已经是 17,它就是前 6 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 1。
第 6 位 · 写入 18：把 17 加上 1 得到 18,写进动态和的第 6 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18]。这个 18 又会成为下一格的累加器 prev,继续往右滚。
第 7 位 · 读 nums[7] = 4：轮到第 7 位。紫色指针落在源数组下标 7,值是 4。右边表里上一格 ans[6] 已经是 18,它就是前 7 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 4。
第 7 位 · 写入 22：把 18 加上 4 得到 22,写进动态和的第 7 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18,22]。这个 22 又会成为下一格的累加器 prev,继续往右滚。
第 8 位 · 读 nums[8] = 2：轮到第 8 位。紫色指针落在源数组下标 8,值是 2。右边表里上一格 ans[7] 已经是 22,它就是前 8 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 2。
第 8 位 · 写入 24：把 22 加上 2 得到 24,写进动态和的第 8 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18,22,24]。这个 24 又会成为下一格的累加器 prev,继续往右滚。
第 9 位 · 读 nums[9] = 3：轮到第 9 位。紫色指针落在源数组下标 9,值是 3。右边表里上一格 ans[8] 已经是 24,它就是前 9 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 3。
第 9 位 · 写入 27：把 24 加上 3 得到 27,写进动态和的第 9 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18,22,24,27]。十个位置全部算完了。
完成 · ans = [2,6,7,10,12,17,18,22,24,27]：十个位置都填满了,回看一遍:累加器从 0 出发,一路是 2、6、7、10、12、17、18、22、24、27,每一步都是在上一步的结果上只加一个新数,绝不回头重算。最终动态和就是 [2,6,7,10,12,17,18,22,24,27]。整道题的窍门就一句:ans[i] = ans[i-1] + nums[i],一个累加器从左扫一遍,线性时间就搞定。
边界:单元素时输出同输入;含负数时前缀和会先降后升;全 0 时动态和也全 0,都按同一套滚动累加处理。
面试重点:前缀和预处理后区间和能 O(1) 求(l 大于 0 取 ans[r]-ans[l-1],l 等于 0 直接取 ans[r]);可原地做到 O(1) 额外空间;三语言差别在 Python 用 accumulate 生成新列表、C++/Java 原地循环改写。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def runningSum(self, nums: List[int]) -> List[int]: return list(accumulate(nums))复杂度
- 时间：O(n)，n 是数组长度。一个指针从左扫到右,每个位置只做一次加法和一次写入,都是常数操作,总共 n 次,所以是线性的 O(n)。本题 n 最大 1000,毫无压力。注意这正是滚动累加的价值:若每格都从头重加一遍会变成 O(n^2)
- 空间：O(1) / O(n)，按峰值算。C++ 和 Java 原地把结果写回 nums,只用了一个循环变量,额外空间是常数 O(1)。Python 用 accumulate 会另开一个长度 n 的新列表,这部分是 O(n);但那是要交出去的输出,若不计返回结果,核心累加逻辑同样只需常数额外空间
易错点
面试追问把动画讲成自己的话
追问算好前缀和到底有什么用,值得专门预处理一遍吗?
追问这题能不能原地做,不额外开数组?
追问三种语言实现上有什么差别?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
好数对的数目
LeetCode 1512 · 简单 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题