Running Sum of an Array
给定一个整数数组 nums。返回一个长度相同的新数组，其中索引 i 处的元素为 nums[0] + nums[1] + ... + nums[i]，也就是前 i+1 个数的总和。
函数
- numsinteger-array
- 要从左到右相加的数字
- 返回值integer-array
- nums 中每个元素对应的累计总和
约束条件
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- 每个累计值都能用 32 位有符号整数表示。
示例
- 输入
- nums = [3, 1, 4, 1, 5]
- 输出
- [3, 4, 8, 9, 14]
- 解释
- 继续相加：
3，然后计算3 + 1 = 4、4 + 4 = 8、8 + 1 = 9和9 + 5 = 14。每个总和都放到最后一个被加数对应的索引处。
- 输入
- nums = [-2, 5, -3]
- 输出
- [-2, 3, 0]
- 解释
- 负数会让总数减少：
-2，然后-2 + 5 = 3，接着3 + (-3) = 0。
- 输入
- nums = [7]
- 输出
- [7]
- 解释
- 单个数字只有一个累计总和，也就是它本身，所以答案是
[7]。
进阶
你能为网格构建同样的结构吗？网格中的每个单元格都保存从左上角到该单元格所构成矩形的总和。
提示
逐个打开提示，每个都会多透露一点。
索引
i处的答案与索引i-1处的答案有什么关系？这两个和恰好相差一个数，即
nums[i]。你不需要再从头开始累加前缀和。保留一个变量
total。从左到右遍历nums，将每个数字加到total中，并将total写入答案中的相同索引位置。
题解
每个答案都是 nums 的一个前缀和，相邻的前缀只相差一个元素。如果每次都从头重新计算前缀，就会重复几乎所有工作。改为向前传递一个总和，这样每个答案只需进行一次加法。
从头开始累加每个前缀
思路
按照定义操作：对于每个索引 i，先将总和设为 0，再把 nums[0] 到 nums[i] 依次相加，并保存结果。这样是正确的，因为每个答案都严格按照定义计算得出。
索引 i 需要进行 i+1 次加法，因此整个数组需要 n(n+1)/2 次加法：当 n = 5000 时，大约需要 1.25 × 10^7 次加法，5000 这个规模是可行的。
算法
- 创建一个长度为
n的答案数组。 - 对于每个索引
i，将total = 0。 - 将从
0到i的每个nums[j]加到total中。 - 将
total存储在答案数组的索引i处，并在最后一个索引处理完后返回答案数组。
def runningSum(nums):
result = []
for i in range(len(nums)):
total = 0
for j in range(i + 1):
total += nums[j]
result.append(total)
return result持续记录总和
思路
前 i+1 个数字的和，等于前 i 个数字的和加上 nums[i]：result[i] = result[i-1] + nums[i]。所以你最多只需要往回看一步，一个变量 total 就够了。对于 [3, 1, 4, 1, 5]，结果依次是 3、4、8、9、14，这就是答案。
每个元素只需要进行一次加法：时间复杂度为 O(n)，除答案外的额外空间复杂度为 O(1)。
算法
- 创建一个长度为
n的答案数组，并设置total = 0。 - 从左到右遍历各个索引，并将
nums[i]加到total中。 - 将
total写入答案数组的索引i处。 - 返回答案。
def runningSum(nums):
result = []
total = 0
for num in nums:
total += num
result.append(total)
return result
易错点和边界情况
- 在循环中重置
total。每个答案都会变成单独的nums[i]，而[3, 1, 4]会原样返回。 - 在
i = 0时读取result[i-1]。大多数语言会越界；Python 会读取最后一个元素，因此原地版本会把最后一个数加到第一个数上。 - 暴力法的内层循环在
j < i时停止。这样会漏掉nums[i]，所以每个答案都会少一个数。 - 在 R 中，用
result <- c(result, total)扩展答案会在每一步复制向量，使快速方法的时间复杂度变为二次。应先分配完整长度。 - 在 C 中，忘记设置
*returnSize = numsSize。这样调用方就不知道要读取多少个总和。
常见问题4
数组的运行总和是什么？
这是一个第二数组，其中每个元素都是第一个数组中截至并包括相同位置的所有元素之和。它也称为前缀和或累积和。[3, 1, 4, 1, 5] 的运行总和是 [3, 4, 8, 9, 14]。
计算累积和的时间复杂度是多少？
时间复杂度为 O(n)，从左到右只需累计一个总和；除答案外，额外空间复杂度为 O(1)。每次都从头重新计算前缀和，时间复杂度为 O(n²)。
你能原地计算累加和吗？
是的。从索引 1 开始遍历到末尾，并设置 nums[i] += nums[i-1]。此时 nums[i-1] 已经保存了截至该位置的所有元素之和，因此每个元素最终都会变成对应的前缀和。原始值会丢失。
前缀和如何帮助进行区间求和查询？
切片 nums[l..r] 的总和是 prefix[r] - prefix[l-1]，当 l = 0 时则是 prefix[r]。对于 [3, 4, 8, 9, 14]，索引 2 到 4 的数相加得到 14 - 4 = 10。经过一次 O(n) 遍历后，每次查询的时间复杂度为 O(1)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def runningSum(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [3, 1, 4, 1, 5]
预期输出
[3, 4, 8, 9, 14]