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]

解题思路

这道题和斐波那契数列有点像，数组 nums，返回的动态和 result，当前数组下标为 i，那么当 i == 0 时 result[0] = nums[0]，当 i >= 1 时 result[i] = nums[i] + result[i + 1]

题解1 （自实现）

时间复杂度 O(n)，空间复杂度 O(n)

class Solution {
    public int[] runningSum(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int item = nums[i];
            if (i == 0) {
                result[i] = item;
            } else {
                result[i] = item + result[i - 1];
            }
        }

        return result;
    }
}

题解 2 （官方示例）

时间复杂度 O(n)，空间复杂度 O(1)，这个解法是对输入数组进行原地操作，虽然节省了空间，但破坏了输入数值，实际开发中该方法不一定可行.

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