# 1480.一维数组的动态和
TIP
标签: 数组、前缀和
# 算法思路
这里我们可以使用「原地修改」的方法,从题目描述中我们可以推导出:
- i = 0, runningSum[i] = nums[0]
- i > 0, runningSum[i] = runningSum[i-1] + nums[i]
找到这个规律,我们可以从下标1开始遍历nums数组,每次让nums[i]
变成 nums[i-1]+nums[i]即可。
function runningSum(nums: number[]): number[] {
let n: number = nums.length;
for (let i = 1; i < n; i++) {
nums[i] += nums[i-1]
}
return nums
};
1
2
3
4
5
6
7
2
3
4
5
6
7
class Solution {
public int[] runningSum(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; i++) {
nums[i] += nums[i - 1];
}
return nums;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 复杂度分析:
- 时间复杂度: O(n), 其中 n 是给定的数组的长度.
- 空间复杂度: O(1)。我们只需要常数的空间保存若干变量.