LeetCode 1480. 一维数组的动态和
题目描述
题意分析
返回一个与输入等长的数组，其中第
i项等于原数组从下标零到i的全部元素之和。每个位置都需要一个累加结果，不是只返回整条数组的总和。当前位置自己的值也包含在和中，第零项的结果就是原来的第零项。输入可能有负数，前缀和因此不一定递增，但累加规则不变。下面的实现直接把结果写回输入数组。
解法：原地前缀和
核心思路
[!blue]
相邻两个前缀只差一个元素：到位置
i的总和，等于到位置i - 1的总和再加上当前位置的原值。因此已经计算过的前缀不必重新求和，可以从左到右逐个延长。原地处理时保持一个明确状态：位置
i左侧都已经保存对应的前缀和，而从i开始的部分仍然保留原值。所以执行nums[i] += nums[i - 1]时，读到的两项恰好分别是当前原值和前一个完整前缀，结果就是当前所需的前缀和。覆盖当前位置不会破坏后续计算。以后的步骤只需要这里已经累计好的总和，不再需要它单独的旧值；右边尚未处理的原值也完全没动。因此不需要另外创建结果数组或保存所有旧值。
第零项已经是自身的前缀和，从下标一开始即可。每次更新后，已完成的前缀又延长一项，遍历结束时整个数组都变成所需结果，直接返回原数组。
解题步骤
- 保持第零个元素不变，它已经是第一个前缀的和。
- 从下标一到末尾依次处理，把上一位置已经算出的前缀和加到当前位置。
- 扫描结束后返回原数组，其所有位置均已保存前缀累加结果。
代码实现
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)。原地保存输出，只使用循环下标，不分配新的结果数组。
关键点总结
[!green]
- 前缀递推复用前一个总和，避免每个位置都重新从头累加。
- 左侧是已处理总和，当前位置仍是原值，遍历方向保证二者含义正确。
- 负数不破坏递推关系，只会使前缀和可能增大也可能减小。
- 返回值复用输入数组，输入内容会被改变。
易错点总结
[!yellow]
- 从右向左更新：左侧尚未成为前缀和，只会得到部分相邻原值之和。
- 从下标零开始读取
i - 1：会访问不存在的位置，应从一开始。- 每个位置都从头再次求和：大量重复计算会把线性处理变为平方量级。
- 只返回最后的总和：题目需要每个前缀的结果，必须保留完整数组。
- 假设输入数组仍保留原值：该实现覆盖输入，后续使用者拿到的已经是前缀和。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 303. 区域和检索 - 数组不可变 | 简单 | 动态和就是区间查询的前缀预处理结果，原题之后还用两前缀之差回答查询。 |
| 1732. 找到最高海拔 | 简单 | 原题只需要累计值的最大值，所以可滚动保存；本题要返回每个前缀结果。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！