1480. 一维数组的动态和
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
力扣1480. 一维数组的动态和
一、题目描述
给你一个数组 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
来源力扣LeetCode
链接https://.cn/problems/running-sum-of-1d-array
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
二、思路分析
这部分可以写写
-
这道题考察了什么思想你的思路是什么
看到这道题目我的第一想法就是再建一个数组然后把原数组中数字用循环相加得到和然后放入新数组中但是这肯定是最基本的解法时间复杂度和空间复杂度都比较大。
后来经过思考我想到了原地修改的解法我们可以遍历数组从下标1开始每次让num[i]变成num[i]+num[i-1]就能够在不需要开辟另一个数组的情况下只遍历一次就可以实现我们的目的了。
-
做题的时候是不是一次通过的遇到了什么问题需要注意什么细节
是一次通过的这道题目只要想清楚了解决起来还是比较简单的毕竟是简单题。
-
有几种解法哪种解法时间复杂度最低哪种解法空间复杂度最低最优解法是什么其他人的题解是什么谁的效率更好一些用不同语言实现的话哪个语言速度最快
也可以使用栈来解决这个问题。
class Solution { public int[] runningSum(int[] nums){ Stack<Integer> currSum = new Stack<>(); currSum.push(nums[0]); for(int i=1;i<nums.length;i++){ int putIndex = currSum.peek()+nums[i]; currSum.push(putIndex); } for(int i=nums.length-1;i>=0;i--){ nums[i]=currSum.pop(); } return nums; } } 作者joettan 链接https://.cn/problems/running-sum-of-1d-array/solution/zhan-jie-gou-zuo-de-suan-fa-zhu-yao-wen-ti-shi-zha/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
感觉空间复杂度和时间复杂度都比较高不过了解一下也可以。
三、AC 代码
func runningSum(nums []int) []int {
n := len(nums)
for i := 1; i < n; i++ {
nums[i] += nums[i-1]
}
return nums
}
四、总结
如果你还有更多的思考、分析、总结通通都加上来吧~
1480. 一维数组的动态和
这道题目可以帮助我们了解前缀和的方法一个月后可以再做一遍。
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |