Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.
- Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].
- Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].
- Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
Constraints:
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6
思路
这里拿第三个例子来作介绍，Input:nums[3,1,2,10,1],Output:[3,4,6,16,17],我们假设获取的结果未get_nums[]
| 计算过程 | 结果 |
|---|---|
| 3 | 3 |
| 3 + 1 | 4 |
| 3+1+2 <=> 4+2 | 6 |
| 3+1+2+10 <=> 6+10 | 16 |
| 3+1+2+10+1 <=> 16+1 | 17 |
- 首先可是无论哪一个例子都有第一个值不变的情况，即get_nums[0] = nums[0]
-
后面的计算过程都可对应成
get_nums[m] = get_nums[m-1] + nums[m] -
由于计算过程在得出get_nums[m]后，不会再次使用nums[m]，我们则可直接取消get_nums[]使用nums[m]来避免内存的开销！
解法
java
class Solution {
public int[] runningSum(int[] nums) {
nums[0] = nums[0];
for(int m = 1; m < nums.length;m++){
nums[m] = nums[m] + nums[m-1];
}
return nums;
}
}
python3
class Solution:
def runningSum(self, nums: List[int]) -> List[int]: #这是新增的语法，为了说明参数和返回值的数据类型。不过仅仅的给人看的，实际上程序并不检查是否是相符的。
nums[0] = nums[0]
m = 1
while m < len(nums):
nums[m] = nums[m] + nums[m-1]
m += 1
return nums
- sample 16ms submission
有点不太明白为啥这个运行较快?
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
var=[]
for i in range(len(nums)):
if i==0:
var.append(nums[i])
else:
var.append(var[i-1]+nums[i])
return var
