1480. 一维数组的动态和

1、题目描述

 2、解决方案

2-1、辅助数组进行解题

• 这个求和过程，尽可能简单，【防止重复计算】，从题目中可以看出，每个数字如果单独计算会出现重复计算，因此可以根据计算的结果，形成递推公式，用辅助数组递推如下：
• dp数组，dp[0] = nums[0];   // 初始化
• dp[n] = dp[n-1] + nums[n];  // 递推过程

class Solution {
    public int[] runningSum(int[] nums) {
        if(nums==null || nums.length == 0) return new int[]{};
        int[] dp = new int[nums.length];
        dp[0]=nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i]=dp[i-1]+nums[i];
        }
        return dp;
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是给定数组长度。

• 空间复杂度：O(n)。 辅助空间dp的长度。

2-2、原地修改，此时的空间复杂度为O（1）

• 此时 i = 0, 返回nums[ 0 ]
• 此时 i > 0, nums[ i ] = nums[ i -1 ] + nums[ i ] ;

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是给定数组长度。

• 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。