一维数组的动态和：一种简单而高效的算法技巧

本篇博客会讲解力扣“1480. 一维数组的动态和”的解题思路，这是题目链接。

本题可以在原数组上进行修改，不需要额外的空间。具体做法是：从数组的第二个元素开始，每个元素都加上它前面的元素，这样就能得到一个动态和数组。例如，对于示例1，数组[1 2 3 4]修改后就变成了[1 3 6 10]。这是因为：2 + 1 = 3，3 + 3 = 6，4 + 6 = 10。用数学公式表示就是：runningSum[i] = runningSum[i-1] + nums[i]，其中runningSum表示修改后的数组，nums表示原数组，i表示下标。这个公式的意义是：原数组从下标为0的元素到下标为i的元素之和等于原数组从下标为0的元素到下标为i-1的元素之和再加上原数组的下标为i的元素。

int* runningSum(int* nums, int numsSize, int* returnSize){
    // 找规律
    // 修改前：[1 2 3 4]
    // 修改后：[1 3 6 10]
    // runningSum[i] = runningSum[i-1] + nums[i]
    for (int i = 1; i < numsSize; ++i)
    {
        nums[i] += nums[i-1];
    }

    *returnSize = numsSize;
    return nums;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

总结

要想解决本题，首先要明白runningSum[i] = runningSum[i-1] + nums[i]这个公式的含义。

感谢大家的阅读！