83.一维数组的动态和（前缀和）_使用动态数组,计算前缀和数组。 前缀和:b[i] = a[1] + a[2]+...a[i], b[

一、题目描述

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

二、解题思路

2.1 方法一：暴力求解

其实这道题可以用暴力解法也是可以的，首先初始化一个数组prefixSum用于存储前缀和，然后定义两个指针i和j：

第一步：当i=0时，表示要计算第一个前缀和，直接将3赋给prefixSum[i]即可，同时i++

第二步：将此时i++的元素和j所指元素进行相加，同时将和赋给prefixSum[i]：

第三步：继续i++，此时i指针指向第三个元素2，那么利用j指针进行遍历，j从0遍历j<i的位置，将所有j遍历的元素与当前i的元素相加:

以此类推，每次i++是为了将每个值赋值prefixSum[i]，利用动态的j每次从0循环到i，将遍历的元素累加就实现了其前面所有元素的相加。

2.2 方法二：动态规划

动态规划，关于动态规划的题前面已经做过很多了，这道题涉及的很简单，简单分析一下：每一个当前的prefixSum[i]都是prefixSum[i-1]+num[i]所得来的，所以遍历整个数组依次计算就行。

三、代码演示

3.1 代码演示一：暴力求解

class Solution {
    public int[] runningSum(int[] nums) {
        //存储结果的数组
        int[] prefixSum = new int[nums.length];
		
        for(int i=0; i<nums.length; i++){
            int sum = 0;
            for(int j=0; j<=i; j++){
                sum += nums[j];
            }
            //每一轮计算的sum赋给当前i多对应的prefixSum
            prefixSum[i] = sum;
        }
        return prefixSum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.2 代码演示二：动态规划

class Solution {
    public int[] runningSum(int[] nums) {
        int[] prefixSum = new int[nums.length];
		//初始化prefixSum[0],因为下面i如果从0开始了，prefixSum[i-1]就是负数了
        prefixSum[0] = nums[0];
        for(int i=1; i<nums.length; i++){
            prefixSum[i] = prefixSum[i-1]+nums[i];
        }
        return prefixSum;
    }
}
1
2
3
4
5
6
7
8
9
10
11