Easy

题目描述

给你一个数组 nums。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i])。

请返回 nums 的动态和。

示例 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, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1]。

示例 3：

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

提示：

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

思路提示：

  • 考虑如何从第 (i-1) 个数字计算出动态和中的第 i 个数字。

解题思路

这道题是典型的前缀和问题，有两种主要解法：

方法一：新建结果数组（推荐）

创建一个新的结果数组，每个位置存储从开头到当前位置的累积和。具体实现：

  • 第一个元素直接复制原数组第一个元素
  • 从第二个元素开始，每个位置的值等于前一个位置的值加上当前原数组的值
  • 这样可以保持代码清晰，易于理解

方法二：原地修改

直接在原数组上进行修改，从第二个元素开始，将每个元素更新为当前元素与前一个元素的和。这种方法可以节省额外的空间，但会修改原数组。

方法三：使用累加变量

维护一个累加变量，遍历数组时不断累加，并将结果存入结果数组。

三种方法的时间复杂度都是O(n)，但在空间使用和代码可读性上有所不同。考虑到题目没有要求原地修改，推荐使用方法一，既保持了代码的清晰性，又不会影响原始数据。

代码实现

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

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        result = [nums[0]]
        for i in range(1, len(nums)):
            result.append(result[-1] + nums[i])
        return result

public class Solution {
    public int[] RunningSum(int[] nums) {
        int[] result = new int[nums.Length];
        result[0] = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            result[i] = result[i-1] + nums[i];
        }
        return result;
    }
}

var runningSum = function(nums) {
    const result = [nums[0]];
    for (let i = 1; i < nums.length; i++) {
        result[i] = result[i-1] + nums[i];
    }
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，n为数组长度
空间复杂度O(n)需要创建结果数组存储动态和