1480. 一维数组的动态和
题目描述
输入整数数组 nums。
返回一个同样长度的数组 runningSum，其中 runningSum[i] 等于 nums[0] 到 nums[i] 所有元素之和，下标从 0 开始。
示例 1
输入：nums = [1,2,3,4] 输出：[1,3,6,10]
解释：依次为 1、1+2、1+2+3、1+2+3+4。
示例 2
输入：nums = [1,1,1,1,1] 输出：[1,2,3,4,5]
解释：每一项是前面若干个 1 的个数。
示例 3
输入：nums = [3,1,2,10,1] 输出：[3,4,6,16,17]
解释：例如第 4 项是 3+1+2+10 = 16。
数据范围
1 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6
解题思路
用一个变量 s 记录到目前为止的累加和。每读到一个 nums[i]，先 s += nums[i]，此时 s 正好是 nums[0..i] 之和，写入 res[i]。这就是前缀和的最基本形式。
为什么正确
处理完下标 i 后，s = nums[0] + … + nums[i] = res[i]。
复杂度分析
时间 O(n)，空间 O(1)（不计答案数组）。
易错点
先累加再写入：如果先写 res[i] = s 再加 nums[i]，结果会整体错一位（变成不含自己的前缀和）。对每个 i 重新求和则会退化成 O(n^2)。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
res = [0] * len(nums)
s = 0
for i, x in enumerate(nums):
s += x
res[i] = s
return resclass Solution {
public int[] runningSum(int[] nums) {
int[] res = new int[nums.length];
int s = 0;
for (int i = 0; i < nums.length; i++) {
s += nums[i];
res[i] = s;
}
return res;
}
}class Solution {
public:
vector<int> runningSum(vector<int>& nums) {
vector<int> res(nums.size());
int s = 0;
for (int i = 0; i < (int)nums.size(); i++) {
s += nums[i];
res[i] = s;
}
return res;
}
};func runningSum(nums []int) []int {
res := make([]int, len(nums))
s := 0
for i, x := range nums {
s += x
res[i] = s
}
return res
}var runningSum = function(nums) {
const res = new Array(nums.length).fill(0);
let s = 0;
for (let i = 0; i < nums.length; i++) {
s += nums[i];
res[i] = s;
}
return res;
};function runningSum(nums: number[]): number[] {
const res: number[] = new Array(nums.length).fill(0);
let s = 0;
for (let i = 0; i < nums.length; i++) {
s += nums[i];
res[i] = s;
}
return res;
}