LeetCode 训练场:1480. 一维数组的动态和

简介: LeetCode 训练场:1480. 一维数组的动态和

1. 题目

1480. 一维数组的动态和


2. 描述

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

3. 思路

先用一个数组 staticSum 来存储最终结果,该数组与 nums 长度相等

然后用一个中间变量 sum 来存放索引位置小于 i 的所有元素和

然后 staticSum 中索引位置为 i 的元素,就是 sum

时间复杂度为 O ( n ) O(n)O(n)

4. 实现

public static int[] runningSum(int[] nums) {
    // 动态和
    int sum = 0;
    // 最终结果
    int[] staticSum = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        staticSum[i] = sum;
    }
    return staticSum;
}
目录
相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
39 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
4月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
118 2
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
39 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
4月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
63 0