一维数组的动态和

一维数组的动态和

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

请返回 nums 的动态和。

这题比较简单，一次遍历就行，我们可以采用累加法，直接就可以得到我们想要的动态和数组；
代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* runningSum(int* nums, int numsSize, int* returnSize){
int i,j;
for(i=1;i<numsSize;i++){
    nums[i]=nums[i]+nums[i-1];
}
*returnSize=numsSize;
return nums;
}
1
2
3
4
5
6
7
8
9
10
11

这里也有一些人参考动态规划算法得到的结果，可以了解

int* runningSum(int* nums, int numsSize, int* returnSize){
    if(numsSize == 0)
    {
        *returnSize = 0;
        return NULL;
    }

    int *dp = (int *)malloc(sizeof(int) * numsSize);
    if(dp == NULL)
    {
        return NULL;
    }

    dp[0] = nums[0];
    for(int i = 1; i < numsSize; i++)
    {
        dp[i] = dp[i - 1] + nums[i];
    }

    *returnSize = numsSize;

    return dp;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24