1、1480. 一维数组的动态和
题目描述
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。 请返回 nums 的动态和。
题目示例
示例 1：
代码语言：javascript复制 输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1 2, 1 2 3, 1 2 3 4] 。示例 2：
代码语言：javascript复制 输入：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：
代码语言：javascript复制 输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]题目解析
很明显，可以看到，返回数组的大小跟输入数组大小一致；其次，输出数组的第一个元素与输入数组第一个元素相同；仔细观察，不难发现，输出数组的第
i个元素等于输出数组的第i-1个元素 输入数组第i个元素。可看作是一个简单动态规划问题。
思路：
- 初始化返回数组大小以及第一个元素
- 遍历输入数组
- 返回结果
官方解析是原地修改输入数组：https://leetcode.cn/problems/running-sum-of-1d-array/solution/yi-wei-shu-zu-de-dong-tai-he-by-leetcode-flkm/
代码实现
代码语言：javascript复制 class Solution {
public int[] runningSum(int[] nums) {
if(nums.length == 0){
return new int[]{0};
}
//初始化返回结果
int[] result = new int[nums.length];
//初始化第一个元素
result[0] = nums[0];
for(int i = 1; i < nums.length; i ){
//第i个元素 = 结果的 i-1个元素 nums[i]
result[i] = result[i - 1] nums[i];
}
return result;
}
}复杂度分析
时间复杂度 O(N)*O*(*N*) ： 遍历 nums 使用线性时间。
空间复杂度 O(1)*O*(1) ： 用于保存结果的 result 是必须使用的空间，此处不计入。
2、724. 寻找数组的中心下标
题目描述
给你一个整数数组 nums ，请计算数组的 中心下标 。 数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。 如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。 如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
题目示例
示例 1：
代码语言：javascript复制 输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] nums[1] nums[2] = 1 7 3 = 11 ，
右侧数之和 sum = nums[4] nums[5] = 5 6 = 11 ，二者相等。示例 2：
代码语言：javascript复制 输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。示例 3：
代码语言：javascript复制 输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] nums[2] = 1 -1 = 0 。题目解析
关键信息：数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
相当于 左侧所有元素相加的和 右侧所有元素相加的和 中心下标的值 = 数组之和
等价于 左侧所有元素相加的和 * 2 中心下标的值 = 数组之和
代码实现
官方计算数组之和采用int sum = Arrays.stream(nums).sum();
class Solution {
public int pivotIndex(int[] nums) {
//如果数组为空，直接返回
if(0 == nums.length){
return 0;
}
int sum= 0;
//遍历输入数组,获取数组之和
for(int i = 0; i < nums.length; i ){
sum = nums[i];
}
//左侧所有元素相加的和等于右侧所有元素相加的和
//那就是 左侧所有元素相加的和 右侧所有元素相加的和 中心元素 = 数组之和
int temp = 0;
for(int i = 0; i < nums.length; i ){
if(2 * temp nums[i] == sum){
return i;
}
temp = nums[i];
}
return -1;
}
}复杂度分析
- 时间复杂度：O(n)，其中 n为数组的长度。
- 空间复杂度：O*(1)。
PS：不定时更新LeetCode的题目，尽量做到每日一更，算法还是要多刷题，想投稿的可以联系我！
