题目描述

给定一个数组 nums。数组动态和的计算公式为：runningSum[i] = sum(nums[0] + ... + nums[i])。

请返回 nums 的动态和。

样例

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4]。

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]。

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

限制

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

算法

(前缀和) $O(n)$

1. 直接计算给定数组的前缀和。

时间复杂度

• 遍历一遍数组，故时间复杂度为 $O(n)$。

空间复杂度

• 在原数组上修改，故仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++)
            nums[i] += nums[i - 1];

        return nums;
    }
};