跳至主要內容

1480. 一维数组的动态和

ITCharge大约 1 分钟

1480. 一维数组的动态和open in new window

  • 标签:数组、前缀和
  • 难度:简单

题目链接

题目大意

描述:给定一个数组 numsnums

要求:返回数组 numsnums 的动态和。

说明

  • 动态和:数组前 ii 项元素和构成的数组,计算公式为 runningSum[i]=x=0x=i(nums[i])runningSum[i] = \sum_{x = 0}^{x = i}(nums[i])
  • 1nums.length10001 \le nums.length \le 1000
  • 106nums[i]106-10^6 \le nums[i] \le 10^6

示例

  • 示例 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]

解题思路

思路 1:递推

根据动态和的公式 runningSum[i]=x=0x=i(nums[i])runningSum[i] = \sum_{x = 0}^{x = i}(nums[i]),可以推导出:

runningSum={nums[0],i=0runningSum[i1]+nums[i],i>0runningSum = \begin{cases} nums[0], & i = 0 \cr runningSum[i - 1] + nums[i], & i > 0\end{cases}

则解决过程如下:

  1. 新建一个长度等于 numsnums 的数组 resres 用于存放答案。
  2. 初始化 res[0]=nums[0]res[0] = nums[0]
  3. 从下标 11 开始遍历数组 numsnums,递推更新 resres,即:res[i] = res[i - 1] + nums[i]
  4. 遍历结束,返回 resres 作为答案。

思路 1:代码

class Solution:
    def runningSum(self, nums: List[int]) -> List[int]:
        size = len(nums)
        res = [0 for _ in range(size)]
        for i in range(size):
            if i == 0:
                res[i] = nums[i]
            else:
                res[i] = res[i - 1] + nums[i]
        return res

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)。一重循环遍历的时间复杂度为 O(n)O(n)
  • 空间复杂度O(n)O(n)。如果算上答案数组的空间占用,则空间复杂度为 O(n)O(n)。不算上则空间复杂度为 O(1)O(1)