有人相爱
有人深夜看海
有人LeetCode第一题都做不出来
小趴菜就是我
女神镇楼压压惊
LeetCode 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] 。 来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/running-sum-of-1d-array
示例3：
输入：nums = [3,1,2,10,1] 输出：[3,4,6,16,17]
提示：
1 <= nums.length <= 1000-10^6 <= nums[i] <= 10^6
解题思路
- 建立一个新的数组存放修改的数据
创立一个新的空数组。则新数组里的newnums[i]数据存放的是nums[0]~nums[i]的和
let sum=0; sum = nums[i]+sum;
将sum一个一个的push放进新数组newnums[]里
- 在原数组上进行修改
除了第一个，nums[i]=nums[i-1]+nums[i];
返回nums
题解
方法一
package Novicevillage.leetcode; /** * @author yinying * @Package Novicevillage.leetcode * @Description: * @Date 2023/1/29 22:01 */ public class Solution { public int[] runningSum(int[] nums) { if(nums.length == 0){ return nums; } for(int i = 1; i < nums.length; i++){ nums[i] = nums[i] + nums[i - 1]; } return nums; } }
方法二
class Solution { public int[] runningSum(int[] nums) { int[] result = new int[nums.length]; result[0] = nums[0]; for(int i = 1; i < result.length; i++){ result[i] = result[i - 1] + nums[i]; } return result; } }
结果展示
内存占用太高，第一题勉强成功
大神题解
执行消耗内存为 0 kb（来自小趴菜的仰望） 的范例
class Solution { public int[] runningSum(int[] nums) { int[] result = new int[nums.length]; result[0] = nums[0]; for(int i = 1; i < result.length; i++){ result[i] = result[i - 1] + nums[i]; } return result; } }
官方题解
思路和算法-原地修改
当 i = 0 时, runningSum[i] = nums[0];
当 i > 0时, runningSum[i] = runningSum[i-1] + nums[i]
代码
class Solution { public: vector<int> runningSum(vector<int>& nums) { int n = nums.size(); for (int i = 1; i < n; i++) { nums[i] += nums[i - 1]; } return nums; } };
复杂度分析
- 时间复杂度：O(n),其中n是给定数组长度。
- 空间复杂度：O(1)。们只需要常数的空间保存若干变量。
