X

LEETCODE 1480. Running Sum of 1d Array 解题思路分析

题目大意:

一维数组的动态和

给你一个数组 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1480

解题思路分析:

这道题实际上求的是前缀和数组。关于前缀数组,我们在之前的很多题目中都运用到过。这里再简单讲解一下。对于前缀和数组中任意一位pre[i],代表nums[0]到nums[i]间所有数字之和,其实我们可以将其看做两部分,即nums[0]到nums[i-1]的和以及nums[i],nums[0]到nums[i-1]的和实际上是pre[i-1],因此可以得出:pre[i]=pre[i-1]+nums[i]。

解题时,我们从下标0处开始计算每一位上的前缀和,默认pre[0]等于nums[i],pre[1]=pre[0]+nums[1],pre[2]=pre[1]+nums[2],以此类推。

实现代码:

public int[] runningSum(int[] nums) {
    int[] pre= new int[nums.length];
    pre[0]=nums[0];
    for(int i=1;i<nums.length;i++){
        pre[i]=pre[i-1]+nums[i];
    }
    return pre;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Running Sum of 1d Array.

Memory Usage: 39.8 MB, less than 50.00% of Java online submissions for Running Sum of 1d Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1480-running-sum-of-1d-array-解题思路分析/
Categories: leetcode
kwantong: