前提条件： 循环不变式 — 本系列的第一篇文章介绍了什么是循环不变式以及如何表述它。如果“循环不变式”这个词对你来说是新的，建议从这里开始。
问题（15秒）
给定一个数组 nums，返回一个数组，其中每个元素是到该索引的累加和。
输入: [1, 2, 3, 4]
输出: [1, 3, 6, 10]
// result[0] = 1
// result[1] = 1 + 2 = 3
// result[2] = 1 + 2 + 3 = 6
// result[3] = 1 + 2 + 3 + 4 = 10
明显的错误
大多数工程师看到这个问题时，会想到在循环中再嵌套一个循环。
“对于每个索引，计算它之前的所有元素的和.” 这是直觉上的反应。虽然从技术上讲是正确的，但这正是导致 O(n²) 代码的思维方式，而 O(n) 的解决方案就在眼前。
// 暴力破解 — 为每个索引从头计算总和
function runningSum(nums: number[]): number[] {
const result: number[] = [];
for (let i = 0; i < nums.length; i++) {
let sum = 0;
for (let j = 0; j <= i; j++) {
sum += nums[j]!;
}
result.push(sum);
}
return result;
}
这段代码的功能是计算一个数组 `nums` 中每个元素之前所有元素的阶乘和，并将结果存储在 `result` 数组中。
O(n²)。对于每个元素，从头开始重新求和。但是在计算result[3]时，你已经知道result[2]了。
你已经做过这些工作。为什么还要再做一次？
领悟的瞬间
你并不是从头开始计算和，而是将一个结果向前传递。
result[i] = result[i-1] + nums[i]
每个运行总和只是前一个运行总和加上当前数字。你不需要向后看——你只需将答案向前传递。这种思维模型的转变——从“重新计算所有内容”到“将上一个答案向前传递”——就是整个洞察力。之后的每个问题都只是它的变体。
这就是运行状态模式：与其从头开始重新计算，不如维护一个随着进展而累积的变量。
不变式
在步骤
i时，sum等于nums[0]到nums[i-1]的总和。
在添加nums[i]之后，sum变成了到nums[i]的总和——这正是result[i]。
让我们追踪一下：
nums = [1, 2, 3, 4]
循环前： sum = 0 → 总和为零 ✓
i=0: sum = 0 + 1 = 1 → 总和为 [1] ✓ → result = [1]
i=1: sum = 1 + 2 = 3 → 总和为 [1,2] ✓ → result = [1,3]
i=2: sum = 3 + 3 = 6 → 总和为 [1,2,3] ✓ → result = [1,3,6]
i=3: sum = 6 + 4 = 10 → 总和为 [1,2,3,4] ✓ → result = [1,3,6,10]
每一步都保持不变。结果是保证正确的。
解决方案
TypeScript:
function runningSum(nums: number[]): number[] {
const result: number[] = [];
let sum = 0;
for (const num of nums) {
sum += num;
result.push(sum);
}
return result;
}
Python:
要求：
1. 保持技术术语的准确性和一致性
2. 保持HTML格式和代码块不变
3. 使用流畅的中文表达
4. 保持原文的专业性和技术性
5. 不要添加或删除内容
def running_sum(nums: list[int]) -> list[int]:
result: list[int] = []
total = 0
for num in nums:
total += num
result.append(total)
return result
复杂度： O(n) 时间，O(n) 空间（用于结果数组）。
就地变体（修改输入）：
function runningSum(nums: number[]): number[] {
for (let i = 1; i < nums.length; i++) {
nums[i]! += nums[i - 1]!;
}
return nums;
}
一切艰难事物的基础
运行总和是最简单的 前缀和 — 在每个索引处存储的运行总和。这个存储的总和是解决一类更复杂问题的关键：
- 子数组和等于 K (#560) — 数组的任何切片是否恰好加起来等于
k? - 区间和查询 (#303) — 索引
i和索引j之间的总和是多少? - 最大子数组 / Kadane 算法 (#53) — 哪个连续切片的和最大?
- 除自身之外的数组乘积 (#238) — 同样的思路，只是用乘法代替加法
你现在不需要知道如何解决这些问题。只需注意：它们每一个都在问一个问题，一旦你预先计算了运行总和，问题就会变得简单得多。唯一改变的问题是操作 — 和、最大值、乘积。向前传递的结构是相同的。
人们跳过这个问题，因为它被标记为“简单”。这就是错误。 “简单”标签衡量的是实现难度，而不是概念的复杂性。 当你遇到子数组和等于 K 时，可能会想知道为什么前缀和感觉不熟悉 — 这是因为你匆忙跳过了引入它们的问题。
不仅仅是这个问题
这背后有一个真正的模式。
当你发现自己在编写一个嵌套循环，而内层循环每次都从索引 0 开始时——这就是信号。你正在重新计算一些你已经知道的东西。解决方法总是相同的：将其存储在一个变量中。
Kadane 算法将最佳和向前传递。滑动窗口将窗口总和向前传递。动态规划将前一个子问题的答案向前传递。不同的问题，不同的名称——但底层的操作是相同的。
形状在变化。原则却没有。
不要重新计算。累积。 运行总和是你第一次看到这个想法。也不会是最后一次。
如何识别这个模式
当你需要累加器模式时：
- 位置
i的答案依赖于所有之前的位置（不仅仅是邻居） - 你发现自己每次都在编写一个内层循环从 0 开始的嵌套循环
- 问题中提到“运行”、“累积”、“前缀”或“到目前为止”
信号：“我正在重新计算一些我已经知道的东西。” 解决方法总是相同的——将其存储在一个变量中。
有一个版本的你能在五分钟内解决这个问题，打勾完成，然后不再想它。那个版本在“子数组和等于K”这个问题上碰到了瓶颈，无法理解为什么前缀和查找感觉如此陌生。
另一个版本在这里停下来。陈述不变式。手动跟踪它。问道：“这个向前推进的思路还出现在什么地方？”那个版本已经掌握了Kadane算法的模式。这个算法在第一次阅读时就很有意义，因为它的结构是熟悉的。
这是一个简单的问题。但这并不意味着它是一个小问题。
你第一次解决这个问题时错过了什么模式——而只有在遇到同一思路的更难版本时才理解到？
系列的下一篇：包含重复元素（#217）——在这里你将学习使用哈希集合的“我之前见过这个吗？”模式。然后是有效的字母异位词（#242），最后是两数之和（#1）——不变式 + 查找 + 累加器，三者结合。