LeetCode 1480. 一维数组的动态和
目录
题目描述
题意分析
给一个整数数组
nums，返回一个等长数组runningSum，其中runningSum[i]等于nums[0] + nums[1] + ... + nums[i]。题面直接把定义写了出来，几乎没有理解成本——这道题的价值在于它是一切区间求和类问题的地基。
约束里有两条值得注意。第一，数组长度到 1000，元素范围是
-10^6到10^6，所以累加和的绝对值最大约 $10^9$，恰好还在 32 位int的范围内（上限约 $2.1 \times 10^9$）。这个「刚好装得下」很值得留意：只要题目稍微放宽长度或数值，就必须换long，面试时主动算一遍这个上界是很好的习惯。第二，元素可以是负数，所以结果序列不保证单调递增，任何依赖单调性的写法都是错的。
输出的语义是「每个位置的前缀和」，等价于把数组原地改造成前缀和数组。题目没有禁止修改入参，也没有要求 $O(1)$ 空间，但看出「可以原地做」是一个加分点。
边界：数组只有一个元素时，答案就是它本身；数组中含负数时结果可能先增后减；全零数组的结果也全是零。题目保证
nums非空（长度至少为 1），所以不需要处理空数组。
解法：原地前缀和
核心思路
暴力写法是对每个
i都从头累加到i，即双重循环，$O(n^2)$。瓶颈显而易见：计算runningSum[5]时，nums[0..4]的和刚刚在算runningSum[4]时就已经求过一遍了，却被完全丢弃。
于是得到本题唯一需要的观察：相邻两个答案之间只差一项。
\[runningSum[i] = runningSum[i-1] + nums[i]\]
这是一条递推式，意味着只要从左到右扫描一遍，每一步复用上一步的结果，就能在 $O(1)$ 的增量代价下得到当前答案。$O(n^2)$ 立刻降到 $O(n)$。
再进一步：递推只依赖紧邻的前一个答案，而
nums[i]在被读取之后就再也不会被用到（后续位置只需要前缀和，不需要单个元素）。因此可以直接把答案写回nums[i]本身，不需要额外开数组。
不变量写清楚：执行完下标
i的这一步后，nums[0..i]里存放的全都是对应位置的前缀和，nums[i+1..]仍是原始值。循环从i = 1开始时不变量已经成立（nums[0]的前缀和就是它自己，无需改动），每轮nums[i] += nums[i-1]把它从i-1推进到i——注意此刻nums[i-1]已经是前缀和（在不变量的左半部分），而nums[i]还是原始值（在右半部分），两者相加恰好就是新的前缀和。
这个「左半已转换、右半未转换」的划分是原地改写类算法的通用心法：只有当读取的位置严格分处不变量两侧、且方向一致时，原地才是安全的。本题从左往右、读左写右，恰好满足。
解题步骤
- 从下标 1 开始遍历，而不是 0。
nums[0]的前缀和就是它自己，天然满足定义，不需要任何操作；从 0 开始会访问nums[-1]，直接越界。这一步也顺带覆盖了「数组只有一个元素」的边界——循环一次都不进，直接返回原数组即可。- 执行
nums[i] += nums[i-1]：读的nums[i-1]已经是前缀和，写的nums[i]还是原始值，相加即得新前缀和。这一行同时完成了「读上一个答案」和「写当前答案」，是不变量推进的全部内容。- 方向必须从左到右：递推依赖的是已经算好的
i-1。如果从右往左，nums[i-1]还是原始值，加出来的只是相邻两项之和，完全不是前缀和。- 返回
nums本身：原地改写后它就是答案数组，不需要额外拷贝。若面试官明确要求「不得修改入参」，就改成新开一个res数组、写成res[i] = res[i-1] + nums[i]，逻辑完全一致，只是空间变成 $O(n)$。
以
nums = [3, 1, 2, 10, 1]走一遍，用竖线标出不变量的分界（左侧是已转换的前缀和，右侧是原始值）。
初始：
3 | 1, 2, 10, 1。下标 0 天然成立。
i = 1：nums[1] = 1 + nums[0] = 1 + 3 = 4。数组变为3, 4 | 2, 10, 1。
i = 2：nums[2] = 2 + nums[1] = 2 + 4 = 6。数组变为3, 4, 6 | 10, 1。
i = 3：nums[3] = 10 + nums[2] = 10 + 6 = 16。数组变为3, 4, 6, 16 | 1。
i = 4：nums[4] = 1 + nums[3] = 1 + 16 = 17。数组变为3, 4, 6, 16, 17 |。
返回
[3, 4, 6, 16, 17]，与期望一致。每一步读到的nums[i-1]都在竖线左侧（已是前缀和），写入的nums[i]都在竖线右侧（还是原值），不变量始终成立。
再用含负数的
nums = [1, -1, 5, -3]检验一次：结果是[1, 0, 5, 2]，序列先降后升再降，说明答案不具备单调性——任何「结果一定递增」的假设都会在这里翻车。
代码实现
class Solution {
public int[] runningSum(int[] nums) {
// 从 1 开始：nums[0] 的前缀和就是它自己，无需处理，也避免访问 nums[-1]。
for (int i = 1; i < nums.length; i++) {
// nums[i-1] 已是前缀和，nums[i] 还是原值，相加即得新前缀和。
nums[i] += nums[i - 1];
}
return nums;
}
}
func runningSum(nums []int) []int {
// 从 1 开始：nums[0] 的前缀和就是它自己，无需处理，也避免访问 nums[-1]。
for i := 1; i < len(nums); i++ {
// nums[i-1] 已是前缀和，nums[i] 还是原值，相加即得新前缀和。
nums[i] += nums[i-1]
}
return nums
}
复杂度分析
- 时间复杂度：$O(n)$，每个位置恰好更新一次。
- 空间复杂度：$O(1)$ 额外空间。返回值就是改写后的输入数组，没有新建长度为 $n$ 的结果数组。
关键点总结
- 前缀状态只保留「到当前位置的累计和」，递推式是
pre[i] = pre[i-1] + nums[i]；它消除了从头重复求和。- 原地改写的安全条件：写入的位置在读取位置之后，且遍历方向与依赖方向一致。想清楚「不变量把数组切成已转换/未转换两半」，就能判断任何原地算法是否会自我污染。
- 从下标 1 起步，让下标 0 由「天然成立」承担。这比在循环里写
if (i == 0)特判更干净，也顺手覆盖了单元素数组。- 本题累计和上界为 $10^9$，32 位
int足够；约束放大时要重新核算并切换到 64 位类型。- 元素可为负 ⇒ 结果不单调。看到前缀和就下意识认为可以二分是常见的思维惯性，只有元素全非负时前缀和才单调、才能二分（209 题就是靠这一点）。
易错点总结
- 循环从
i = 0开始：执行nums[0] += nums[-1]，Java 抛ArrayIndexOutOfBoundsException，Go 直接 panic。- 从右往左遍历：
nums = [3, 1, 2, 10, 1]中i = 4时nums[3]还是原始的 10，得到nums[4] = 11；一路做下来结果是[3, 4, 3, 12, 11]，全是相邻两项之和而非前缀和。- 写成
nums[i] = nums[i-1]（漏了+=的加号）：数组被填成全是首元素，[3, 1, 2, 10, 1]输出[3, 3, 3, 3, 3]。- 用一个独立变量累加却忘了写回：例如
sum += nums[i]但没有nums[i] = sum，返回的还是原数组[3, 1, 2, 10, 1]。- 新开结果数组时写成
res[i] = nums[i-1] + nums[i]：读的是原数组的前一项而非结果数组的前一项，[3, 1, 2, 10, 1]输出[3, 4, 3, 12, 11]，同样退化成相邻两项之和。- 误以为结果一定递增并据此二分查找：
nums = [1, -1, 5, -3]的前缀和是[1, 0, 5, 2]，非单调，二分会返回错误位置。- 把题意误解为「滑动窗口和」或「相邻两数之和」：
[3, 1, 2, 10, 1]会输出[4, 3, 12, 11]这类长度为n-1的数组，长度就先对不上了。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 303. 区域和检索 - 数组不可变 | 简单 | 把前缀和封装成类，用 pre[r+1] - pre[l] 做 $O(1)$ 区间查询 |
| 724. 寻找数组的中心下标 | 简单 | 需要同时用到前缀和与总和，靠 total - pre - nums[i] 得到右半和 |
| 560. 和为 K 的子数组 | 中等 | 前缀和配哈希表统计配对，重点在空前缀入表与先查后写的顺序 |
| 238. 除了自身以外数组的乘积 | 中等 | 把加法换成乘法且需前后两趟扫描，禁用除法是核心限制 |
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 升到二维，查询要用容斥原理做四项加减 |
| 1685. 有序数组中差绝对值之和 | 中等 | 借前缀和把每个位置的绝对差之和拆成左右两段的线性表达式 |