[!info] related notes

前缀和

前缀和的英文名非常直观，就叫 Prefix Sum（有时候也会被称为 Cumulative Sum，即累加和）。

它是算法和数据结构中一个极其重要且精妙的技巧。如果说“滑动窗口”是用来解决单调性连续子数组问题的，那么“前缀和”就是用来降维打击频繁求区间和问题的神器。

1. 前缀和的本质：记账思维（空间换时间）

想象你正在记账，下面是你这周前 5 天的每天开销（相当于原数组 nums）：

• nums = [10, 20, 10, 30, 10] （第 1 天花 10 块，第 2 天花 20 块…）

如果我现在问你：“第 2 天到第 4 天，你一共花了多少钱？”

人类的直觉（也是最暴力的算法）是：把第 2、3、4 天的钱重新加一遍：$20 + 10 + 30 = 60$。

如果我问 1000 次不同区间的花费，你就得去原数组里循环加 1000 次。时间复杂度是 $O(N)$。

前缀和的思维是：在记账的同时，顺便算出一个“截至今日的总花销”。

构建一个新的数组 prefix，它的每一项代表从第 1 天到第 $i$ 天的总和：

• 第 1 天总计：10
• 第 2 天总计：10 + 20 = 30
• 第 3 天总计：30 + 10 = 40
• 第 4 天总计：40 + 30 = 70
• 第 5 天总计：70 + 10 = 80

所以，你的前缀和数组长这样：

prefix = [10, 30, 40, 70, 80]

这个时候，我再问你：“第 2 天到第 4 天，一共花了多少钱？”

你不需要再去挨个加了。你只需要拿**“前 4 天的总花费”减去“前 1 天的总花费”**就行了！

公式：prefix[第4天] - prefix[第1天] = $70 - 10 = 60$。

只要前缀和数组构建完成，以后无论我问你哪个区间的和，你都可以通过一次减法瞬间算出来，查询的时间复杂度被压缩到了完美的 $O(1)$！

2. 前缀和的万能公式

假设我们有一个数组 nums，它的前缀和数组叫 prefix。

prefix[i] 表示：从 nums[0] 加到 nums[i] 的总和。

那么，如果你想求 nums 数组中从下标 $L$ 到下标 $R$（包含 $L$ 和 $R$）的连续子数组的和，公式永远是：

$$ Sum(L, R) = prefix[R] - prefix[L - 1] $$

(注意：当 $L = 0$ 时，前面没有元素可以减，所以这就是为什么我们在上一题 LC 560 的代码中，要提前在 Map 里塞一个 prefixMap.set(0, 1)，相当于虚构了一个 prefix[-1] = 0 来做兜底计算。)

3. 前缀和的两大流派

在算法题中，前缀和通常有两种完全不同的玩法：

• 流派一：前缀和数组（区间查询）

  这是最基础的用法。题目往往会给你一个庞大的数组，然后频繁地问你“区间 [i, j] 的和是多少”。这种题你只需要老老实实把 prefix 数组建出来，然后套上面的公式做减法就行。经典题目：力扣 303 题《区域和检索 - 数组不可变》。

• 流派二：前缀和 + 哈希表（寻找目标和）

  这就是你刚刚做的那道 560 题《和为 K 的子数组》。这种题的难点在于，它不是问你某个区间的和，而是让你找出和等于 $k$ 的所有区间。

  这时候公式 $Sum(L, R) = prefix[R] - prefix[L - 1] = k$ 就要变个魔术了，移项变成：

  $$

prefix[L - 1] = prefix[R] - k

$$

这意味着，我们不需要真正的建一个数组存起来，只需要边遍历边计算当前的 `prefix[R]`，然后去哈希表（Map）里查：**以前有没有出现过大小刚好等于 `prefix[R] - k` 的值？** 有的话，就说明找到了合法的子数组！