一维数组的动态和 图解题解
这道题到底在问什么
- 输入
- nums=[1,2,3,4]
- 输出
- [1,3,6,10]
- 输入
- nums=[1,1,1,1,1]
- 输出
- [1,2,3,4,5]
- 输入
- nums=[3,1,2,10,1]
- 输出
- [3,4,6,16,17]
最优解：一步一步想明白
- 3记牢一句:ans[i] = ans[i-1] + nums[i],第 0 位就是 nums[0]。一个累加器从左滚到右,扫一遍全部前缀和都出来。下面每帧都在套这句。
- 4先看清画面。上面是源数组 nums = [2,4,1,3,2,5,1,4,2,3],一共 10 个数。右边那张表是要填的动态和 ans,现在还是空的。我们准备一个累加器,起始值是 0,然后让紫色指针从下标 0 开始一格一格往右走,每走一格就把当前数加进累加器,得到的就是这一格的前缀和,记进右边的表。先从第 0 位开始。
- 5从第 0 位开始。紫色指针落在源数组下标 0,值是 2。它前面没有任何数,所以这一格的动态和起点就是它自己,累加器此刻是 0,等会儿 0 加上 2 就是 ans[0]。
- 6把 0 加上 2 得到 2,写进动态和的第 0 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2]。这个 2 又会成为下一格的累加器 prev,继续往右滚。
- 7轮到第 1 位。紫色指针落在源数组下标 1,值是 4。右边表里上一格 ans[0] 已经是 2,它就是前 1 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 4。
- 8把 2 加上 4 得到 6,写进动态和的第 1 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6]。这个 6 又会成为下一格的累加器 prev,继续往右滚。
- 9轮到第 2 位。紫色指针落在源数组下标 2,值是 1。右边表里上一格 ans[1] 已经是 6,它就是前 2 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 1。
- 10把 6 加上 1 得到 7,写进动态和的第 2 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7]。这个 7 又会成为下一格的累加器 prev,继续往右滚。
- 11轮到第 3 位。紫色指针落在源数组下标 3,值是 3。右边表里上一格 ans[2] 已经是 7,它就是前 3 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 3。
- 12把 7 加上 3 得到 10,写进动态和的第 3 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10]。这个 10 又会成为下一格的累加器 prev,继续往右滚。
- 13轮到第 4 位。紫色指针落在源数组下标 4,值是 2。右边表里上一格 ans[3] 已经是 10,它就是前 4 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 2。
- 14把 10 加上 2 得到 12,写进动态和的第 4 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12]。这个 12 又会成为下一格的累加器 prev,继续往右滚。
- 15轮到第 5 位。紫色指针落在源数组下标 5,值是 5。右边表里上一格 ans[4] 已经是 12,它就是前 5 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 5。
- 16把 12 加上 5 得到 17,写进动态和的第 5 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17]。这个 17 又会成为下一格的累加器 prev,继续往右滚。
- 17轮到第 6 位。紫色指针落在源数组下标 6,值是 1。右边表里上一格 ans[5] 已经是 17,它就是前 6 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 1。
- 18把 17 加上 1 得到 18,写进动态和的第 6 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18]。这个 18 又会成为下一格的累加器 prev,继续往右滚。
- 19轮到第 7 位。紫色指针落在源数组下标 7,值是 4。右边表里上一格 ans[6] 已经是 18,它就是前 7 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 4。
- 20把 18 加上 4 得到 22,写进动态和的第 7 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18,22]。这个 22 又会成为下一格的累加器 prev,继续往右滚。
- 21轮到第 8 位。紫色指针落在源数组下标 8,值是 2。右边表里上一格 ans[7] 已经是 22,它就是前 8 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 2。
- 22把 22 加上 2 得到 24,写进动态和的第 8 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18,22,24]。这个 24 又会成为下一格的累加器 prev,继续往右滚。
- 23轮到第 9 位。紫色指针落在源数组下标 9,值是 3。右边表里上一格 ans[8] 已经是 24,它就是前 9 个数的和,我把它当作累加器 prev 拿过来,接下来只要再加上当前这个 3。
- 24把 24 加上 3 得到 27,写进动态和的第 9 位,源数组里这一格标成绿色表示已经处理过。右边 ans 现在是 [2,6,7,10,12,17,18,22,24,27]。十个位置全部算完了。
- 25十个位置都填满了,回看一遍:累加器从 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],一个累加器从左扫一遍,线性时间就搞定。
⚠️ 容易写错的地方
✗ 错：每算一格都从 nums[0] 重新累加到 nums[i],写成两层循环
✓ 对：利用上一格的结果滚动:ans[i] = ans[i-1] + nums[i],只加一次
前缀和的精髓就是复用。ans[i-1] 已经把前 i 个数加好了,算 ans[i] 时只差最后那个 nums[i],没必要把前面再加一遍。从头重加会让时间从 O(n) 退化成 O(n^2),数据一大就慢
✗ 错：忘了第 0 位,直接从 i=1 开始填,导致 ans[0] 空着
✓ 对：ans[0] 前面没有数,起点就是 nums[0] 本身(相当于 prev = 0)
第 0 个前缀和没有左邻居可加,它的值就是 nums[0]。原地写法里 nums[0] 本来就是它自己,循环从 i=1 开始正好不动它;但如果你另开数组,一定要先把 ans[0] 设成 nums[0] 再往后滚
✗ 错：原地覆盖时担心 nums[i-1] 被改坏了会算错
✓ 对：从左往右的顺序保证读到 nums[i-1] 时它已是前缀和,正是我们要的
原地写法里 nums[i-1] 确实被改成了前缀和,但这恰好是我们需要的累加器。只要严格从左到右推进,每次读的左邻居都是已经算好的结果,顺序一变(比如从右往左)才会出错
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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))C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) nums[i] += nums[i - 1];
return nums;
}
};Java
import java.util.*;
class Solution {
public int[] runningSum(int[] nums) {
for (int i = 1; i < nums.length; ++i) {
nums[i] += nums[i - 1];
}
return 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);但那是要交出去的输出,若不计返回结果,核心累加逻辑同样只需常数额外空间
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 一维数组的动态和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
算好前缀和到底有什么用,值得专门预处理一遍吗?+
太有用了,前缀和是一个非常基础的工具。一旦把动态和 ans 预处理好,任意一段区间 [l, r] 的元素之和都能在常数时间里直接拿到:当 l 大于 0 时用 ans[r] 减 ans[l-1],当 l 等于 0 时区间从头开始,直接取 ans[r] 就是答案,不必每次都把这段重新加一遍。也就是说花一次 O(n) 预处理,换来之后无数次区间求和都是 O(1)。很多看起来复杂的题,比如子数组和、二维区域和,底层都是靠前缀和加速的,所以它值得专门记牢。
这题能不能原地做,不额外开数组?+
能,而且 C++ 和 Java 的参考写法就是原地的。从下标 1 开始,让 nums[i] 加上 nums[i-1],把前缀和直接写回原数组,最后返回 nums,额外空间是常数 O(1)。关键在于从左往右推进时,左边那一格已经被改成前缀和了,正好当累加器用。Python 也可以这样原地循环,只是参考解图省事用了 accumulate,它会另开一个新列表,空间是 O(n)。
三种语言实现上有什么差别?+
Python 最短,一行 list(accumulate(nums)),把累加交给标准库,代价是生成一个新列表。C++ 和 Java 几乎一样,都是一个 for 循环从下标 1 开始执行 nums[i] += nums[i-1],原地把答案写回 nums 再返回,不额外开空间。逻辑三家完全一致,都是滚动累加,差别只在 Python 借标准库生成新列表、C++ 和 Java 手写循环原地改写。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 一维数组的动态和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。