题目描述
思路解析
一句话答案：LeetCode 1480 一维数组的动态和：新数组第 i 位是 nums 前 i+1 个数之和，靠前缀和边扫边累加、每格只在上一格结果上添一个新数不重算，时间 O(n)、空间 O(1)。
动态和的每一格该填什么
给一个数组 nums，要返回一个等长的新数组，第 i 个位置放的是 nums 从开头一直加到第 i 个的总和：第 0 位就是 nums[0]，第 1 位是 nums[0]+nums[1]，越往后加进来的数越多。题面 nums=[1,2,3,4] 得 [1,3,6,10]，nums=[3,1,2,10,1] 得 [3,4,6,16,17]。
每格从头加一遍，慢在哪里
到第 i 位就从 nums[0] 加到 nums[i]，每格都当成一道独立的求和题——第 0 位加 1 个数、第 1 位加 2 个，直到末位加满 n 个。这些次数摞起来是 1+2+…+n，落在 O(n²) 量级。数组短时无所谓，一旦长到上千，同一段开头被反复重加，大多加法都在白做。
前缀和凭什么每格只加一次
相邻两格的和其实只差一个数。第 i 位是前 i+1 个数的和，第 i−1 位是前 i 个数的和，两者之间只差最后进来的那个 nums[i]。上一格已把前面整段加好，算这一格拿它再补一个 nums[i] 就够，不必回头重算。这种累计下来的和就叫前缀和，滚动公式是 ans[i] = ans[i-1] + nums[i]：累加器从左滚到右扫一遍，每格只做一次加法，前面的和一次都不重来。
累加器从左滚到右，每步做两件事
走起来只有两个动作。先定累加器的起点：第 0 位左边没有数，前缀和就是 nums[0] 自己，相当于从 0 加上 nums[0]。然后从第 1 位起，每到一格就把累加器，也就是上一格的前缀和，加上当前的 nums[i]；得到的新和写进这一格，也顺势成为下一格的累加器。一路推进到末位，前缀和就都填满了。
题面两组数，逐格滚给你看
先走 nums=[1,2,3,4]。累加器从 0 起步：第 0 位 0+1=1；第 1 位 1+2=3；第 2 位 3+3=6；第 3 位 6+4=10，得到 [1,3,6,10]。每步都是拿左边刚算出的结果，只添一个新数。
再走 nums=[3,1,2,10,1]。第 0 位就是 3；第 1 位 3+1=4；第 2 位 4+2=6；第 3 位 6+10=16；第 4 位 16+1=17，最终是 [3,4,6,16,17]。哪怕中间夹着大得多的 10，也只是在上一格 6 上加一次，前面几个数不必再碰。
别漏了第 0 位，也别从右往左滚
另开新数组时最易漏的，是忘了先把第 0 位设成 nums[0] 就从第 1 位开填，开头空一格、整串全错位；原地写法从下标 1 起让 nums[i] 加上 nums[i-1]，正好绕开——nums[0] 本就是它自己。方向也不能反：从左往右时读到的 nums[i-1] 已是算好的前缀和，当得起累加器，一改成从右往左，左邻居还没更新就取错了。复杂度上只一趟扫描、每格一次加法，时间 O(n)；原地写回 nums 时空间 O(1)，Python 的 accumulate 会另开长度 n 的列表作输出。边界同样一套滚法：单个元素时输出同输入；夹负数时前缀和先降再升；全 0 时动态和也全 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢一句: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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题