题目描述:
给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。
from typing import List
x = [1,2,3,4]
def runningSums(nums: List[int]) -> List[int]:
'''
请在此处将函数补充完整
'''
print(runningSums(nums = x))
示例1:
输入:[1, 2, 3, 4]
输出:[1, 3, 6, 10]
过程简析:[1, 1+2, 1+2+3, 1+2+3+4]
示例2:
输入:[1, 1, 1, 1, 1, 1]
输出:[1, 2, 3, 4, 5, 6]
过程简析:[1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1, 1+1+1+1+1+1]
解题思路:
我们设函数输入的数组为 nums[ ],长度为 n+1 ,函数返回的数组为 a[ ]
则:
a[0] = nums[0]
a[1] = nums[0] + nums[1]
a[2] = nums[0] + nums[1] + nums[2]
a[3] = nums[0] + nums[1] + nums[2] + nums[3]
...
a[n] = nums[0] + ... + nums[n]
我们不难从中发现规律,将运算简化一下:
a[0] = nums[0]
a[1] = a[0] + nums[1]
a[2] = a[1] + nums[2]
a[3] = a[2] + nums[3]
...
a[n] = a[n-1] + nums[n]
因此,可以编写代码如下:
a = []
a.append(nums[0])
for i in range(1, len(nums)):
a.append(nums[i]+a[i-1])
return a
在此基础上,代码可以进一步简化,把中间商 “a” 给去掉:
for i in range(1, len(nums)):
nums[i] += nums[i-1]
return nums