前缀和完全指南 - 掌握 O(1) 时间复杂度的区间查询

概述

前缀和是算法面试中最强大且简单的优化技术之一。它将 O(n) 的区间和查询转换为 O(1) 的操作，对以下场景至关重要：

区间和查询
子数组和问题
连续数组问题
二维矩阵和查询

为什么面试官喜欢考它：测试你使用预处理和时空权衡来优化暴力解法的能力。

⏱️ 时间复杂度

构建：O(n) — 一次遍历计算前缀和
查询：O(1) — 常数时间区间和

💾 空间复杂度

O(n) — 存储前缀和数组

📋 使用场景

对同一数组进行多次区间和查询
查找具有特定和属性的子数组
二维矩阵和查询
任何涉及”连续子数组和”的问题

核心概念：累积和

核心思想：预计算累积和，使任何区间和都变成简单的减法运算。

什么是前缀和？

给定数组 nums，前缀和数组 prefix 满足：

\text{prefix}[i] = \sum_{j=0}^{i-1} \text{nums}[j]

简单来说：

prefix[0] = 0（零个元素的和）
prefix[1] = nums[0]
prefix[2] = nums[0] + nums[1]
prefix[i] = 前 i 个元素的和

直观理解

原数组：   [2,  4,  -1,  5,  3]
索引：      0   1    2   3   4

前缀和：   [0,  2,  6,  5, 10, 13]
索引：      0   1   2   3   4   5
            ↑
         基础情况

每个 prefix[i] 存储索引 i 之前所有元素的和。

神奇的公式

获取区间 [left, right] 的和：

\text{sum}[\text{left}, \text{right}] = \text{prefix}[\text{right} + 1] - \text{prefix}[\text{left}]

为什么？

prefix[right + 1] = nums[0] + nums[1] + ... + nums[right]
prefix[left]      = nums[0] + nums[1] + ... + nums[left-1]
                    ────────────────────────────
相减得到：          nums[left] + ... + nums[right]  ✓

构建前缀和数组

💡 算法

创建大小为 n + 1 的数组（多一个用于基础情况）
设置 prefix[0] = 0
对于每个索引 i，计算 prefix[i + 1] = prefix[i] + nums[i]

🎮 交互式可视化

逐步观看前缀和数组是如何构建的。

Building Prefix Sum Array

Step 1 / 7

Initial array: We want to build a prefix sum array

Original Array:

-1

Prefix Sum Array:

Current element being processed

Current prefix sum being calculated

💻 模板代码

✅ 关键点

大小：前缀数组有 n + 1 个元素（比原数组多一个）
基础情况：prefix[0] = 0 表示空前缀
递推关系：prefix[i + 1] = prefix[i] + nums[i]
时间：O(n) 构建
空间：O(n) 额外空间

O(1) 区间和查询

一旦构建了前缀和，任何区间查询都只需常数时间！

💡 公式

sum[left, right] = prefix[right + 1] - prefix[left]

🎮 交互式可视化

看看如何使用前缀和计算区间和。

Range Sum Query

Step 1 / 3

Query: Find sum of range [1, 3] (indices 1 to 3)

Original Array:

-1

Prefix Sum Array:

Query range in original array

Prefix sum values used in calculation

💻 模板代码

📊 示例详解

nums = [2, 4, -1, 5, 3]
prefix = [0, 2, 6, 5, 10, 13]

查询：[1, 3] 的和
─────────────────────
sum[1, 3] = prefix[4] - prefix[1]
          = 10 - 2
          = 8

验证：nums[1] + nums[2] + nums[3]
    = 4 + (-1) + 5
    = 8 ✓

为什么是 prefix[4] 而不是 prefix[3]？

因为 prefix[i] 表示索引 i 之前（不包含）的和。

prefix[4] = 索引 [0, 3] 的和
prefix[1] = 索引 [0, 0] 的和
相减 = 索引 [1, 3] 的和 ✓

子数组和模式

前缀和最强大的应用：查找具有特定和的子数组。

核心洞察

子数组 [i, j] 的和为 k：

\text{prefix}[j + 1] - \text{prefix}[i] = k

重新整理：

\text{prefix}[i] = \text{prefix}[j + 1] - k

关键思想：遍历时，检查 (当前和 - k) 是否在历史记录中！

哈希表技巧

使用哈希表存储：

键：前缀和值
值：出现次数（或索引）

🎮 交互式可视化

观看如何使用哈希表找到目标和的子数组。

Finding Subarray with Target Sum

Step 1 / 5

Find subarray with sum = 4. Array: [2, 4, -1, 5, 3]

Original Array:

-1

Prefix Sum Array:

Current position being checked

Found subarray matching target sum

模板模式

function subarraySum(nums, target) {
  const map = new Map();
  map.set(0, 1);  // 基础情况：空前缀
  
  let count = 0;
  let sum = 0;
  
  for (const num of nums) {
    sum += num;
    
    // 检查 (sum - target) 是否存在
    if (map.has(sum - target)) {
      count += map.get(sum - target);
    }
    
    // 将当前和加入哈希表
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  
  return count;
}

为什么有效

在每个位置 j，我们知道：
  - 当前前缀和 = sum
  - 我们想要和为 k 的子数组
  - 需要：prefix[i] = sum - k
  
如果哈希表中存在 (sum - k)：
  → 找到了从某个 i 到 j 和为 k 的子数组！

面试题目

问题一：区域和检索 - 数组不可变 (LC 303)

问题：设计一个数据结构来高效计算区间和。

给定 nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) → 1  ((-2) + 0 + 3)
sumRange(2, 5) → -1 (3 + (-5) + 2 + (-1))
sumRange(0, 5) → -3 (所有元素)

解法：经典前缀和应用！

复杂度：

构造函数：O(n) 时间，O(n) 空间
sumRange：O(1) 时间

面试提示：这是基础题目，先掌握这个！

问题二：和为 K 的子数组 (LC 560)

问题：计算和等于 k 的连续子数组数量。

输入：nums = [1, 2, 3], k = 3
输出：2
解释：子数组 [1, 2] 和 [3]

输入：nums = [1, 1, 1], k = 2
输出：2
解释：子数组 [1, 1]（两次）

关键洞察：使用哈希表跟踪前缀和频率。

复杂度：O(n) 时间，O(n) 空间

逐步示例

nums = [1, 2, 3], k = 3
map = {0: 1}  (基础情况)

i=0, num=1:
  sum = 1
  complement = 1 - 3 = -2 (不在哈希表中)
  map = {0: 1, 1: 1}
  count = 0

i=1, num=2:
  sum = 3
  complement = 3 - 3 = 0 (在哈希表中找到！)
  count += map[0] = 1
  map = {0: 1, 1: 1, 3: 1}
  count = 1

i=2, num=3:
  sum = 6
  complement = 6 - 3 = 3 (在哈希表中找到！)
  count += map[3] = 1
  map = {0: 1, 1: 1, 3: 1, 6: 1}
  count = 2

返回 2 ✓

常见错误：忘记 map.set(0, 1) 基础情况！

问题三：连续数组 (LC 525)

问题：找到 0 和 1 数量相等的最长子数组。

输入：nums = [0, 1, 0]
输出：2
解释：[0, 1] 或 [1, 0]

输入：nums = [0, 1, 1, 0, 1, 1, 1, 0]
输出：4
解释：[1, 0, 1, 1] 或 [0, 1, 1, 0]

关键洞察：转换问题！

将 0 替换为 -1
问题变成：找和为 0 的最长子数组

复杂度：O(n) 时间，O(n) 空间

为什么有效

原数组：[0, 1, 0, 1, 1, 0]
转换后：[-1, 1, -1, 1, 1, -1]
前缀和：[0, -1, 0, -1, 0, 1, 0]
           ↑       ↑
        相同的值！

当前缀和重复时：
  → 它们之间的元素和为 0
  → -1 和 1 的数量相等
  → 原数组中 0 和 1 的数量相等 ✓

面试提示：转换为更简单的问题是关键技能！

问题四：和可被 K 整除的子数组 (LC 974)

问题：计算和可被 k 整除的子数组数量。

输入：nums = [4, 5, 0, -2, -3, 1], k = 5
输出：7

关键洞察：使用取模运算！

如果两个前缀和除以 k 的余数相同：

它们的差可被 k 整除
它们之间的子数组和可被 k 整除！

复杂度：O(n) 时间，O(k) 空间

为什么取模有效

prefix[i] % k = r
prefix[j] % k = r  (相同余数)

那么：
  (prefix[j] - prefix[i]) % k = 0
  → sum[i+1, j] 可被 k 整除 ✓

关键细节：处理负数取模！

let mod = sum % k;
if (mod < 0) mod += k;  // 转为正数

在 Java/JavaScript 中，-7 % 5 = -2，但我们需要 3。

问题五：统计「1 比 0 多」的子数组数目 (LC 2031) 🔒

注意：这是一道 LeetCode 会员题。需要订阅才能在平台上提交。

问题：给定一个二进制数组，统计 1 的数量严格大于 0 的数量的非空子数组数目。

输入：nums = [0, 1, 1, 0, 1]
输出：9

输入：nums = [1, 1, 1]
输出：6（所有 6 个非空子数组）

核心洞察：这是一道巧妙结合前缀和与 O(n) 观察的精彩题目！

第一步：问题转换

转换：0 → -1，1 → 1
问题变成：统计和 > 0 的子数组
关键关系：子数组 [i, j] 和 > 0 ⟺ prefixSum[j] > prefixSum[i-1]

对于每个位置 j，我们需要统计有多少个 i 使得 prefixSum[i-1] < prefixSum[j]。

第二步：O(n) 的突破！💡

为什么 O(n) 可行？

转换后，数组只包含 1 和 -1，因此：

每个前缀和恰好变化 +1 或 -1
我们可以动态维护小于当前前缀和的前缀和个数！

关键变量：

currSum：当前前缀和
ltCurrSum：小于 currSum 的前缀和总个数
sumCount：每个前缀和值的出现频率

算法逻辑

当遇到 0（变成 -1）：

旧 currSum: 5
减 1 后：currSum = 4

之前：ltCurrSum 统计了所有 < 5 的前缀和
现在：某些 = 4 的前缀和不再 < currSum
→ 减去 = 4 的前缀和个数

当遇到 1：

旧 currSum: 5
加 1 后：currSum = 6

之前：ltCurrSum 统计了所有 < 5 的前缀和
现在：所有 < 5 的前缀和仍然 < 6
     并且 = 5 的前缀和现在也 < 6 了！
→ 加上 = 5 的前缀和个数

复杂度：O(n) 时间，O(n) 空间 — 比 O(n log n) 的树状数组解法更优！

详细示例

nums = [0, 1, 1, 0, 1]
转换后：[-1, 1, 1, -1, 1]

初始化：
  sumCount = {0: 1}  (基础情况)
  currSum = 0
  ltCurrSum = 0
  result = 0

位置 0 (num=0 → -1)：
  currSum: 0 → -1
  ltCurrSum -= sumCount[-1] = 0 - 0 = 0
  sumCount = {0: 1, -1: 1}
  result += 0 → result = 0

位置 1 (num=1)：
  ltCurrSum += sumCount[-1] = 0 + 1 = 1
  currSum: -1 → 0
  sumCount = {0: 2, -1: 1}
  result += 1 → result = 1
  (找到子数组 [1])

位置 2 (num=1)：
  ltCurrSum += sumCount[0] = 1 + 2 = 3
  currSum: 0 → 1
  sumCount = {0: 2, -1: 1, 1: 1}
  result += 3 → result = 4
  (找到子数组 [1,1], [0,1,1], 从开头的 [1,1])

位置 3 (num=0 → -1)：
  currSum: 1 → 0
  ltCurrSum -= sumCount[0] = 3 - 2 = 1
  sumCount = {0: 3, -1: 1, 1: 1}
  result += 1 → result = 5

位置 4 (num=1)：
  ltCurrSum += sumCount[0] = 1 + 3 = 4
  currSum: 0 → 1
  sumCount = {0: 3, -1: 1, 1: 2}
  result += 4 → result = 9

返回 9 ✓

为什么有效：增量属性

关键观察：0 → -1 转换后：

前缀和每步只变化 ±1
从 currSum 移动到 currSum+1 或 currSum-1
我们可以增量更新 ltCurrSum！

直观理解：

已见前缀和：[-1, 0, 0, 1]
当 currSum = 1 时：
  ltCurrSum = 3（三个前缀和 < 1）

下一个 num = 1，currSum 变成 2：
  旧的 < 1：仍然 < 2 ✓
  旧的 = 1：现在 < 2 ✓
  → ltCurrSum += count(1)

下一个 num = -1，currSum 变成 0：
  旧的 < 1：有些 = 0，不再 < currSum
  → ltCurrSum -= count(0)

与 O(n log n) 解法比较

方法	时间	空间	难度
本 O(n) 解法	O(n)	O(n)	中等（巧妙！）
树状数组	O(n log n)	O(n)	困难
归并排序	O(n log n)	O(n)	困难

面试技巧：先讲 O(n log n) 的树状数组解法，如果时间允许再提及 O(n) 优化！

常见错误

❌ 错误：currSum 减少时忘记减去计数

if (num === 0) {
  currSum--;
  // 缺少：ltCurrSum -= sumCount.get(currSum) || 0;
}

❌ 错误：在使用 ltCurrSum 之前更新 sumCount

sumCount.set(currSum, ...);  // 太早了！
result += ltCurrSum;  // ltCurrSum 需要旧状态

✅ 正确：更新 ltCurrSum → 更新 sumCount → 累加到 result

二维前缀和（进阶）

将前缀和扩展到二维矩阵，实现 O(1) 矩形和查询！

问题六：二维区域和检索 (LC 304)

问题：高效计算任意子矩形内元素的和。

矩阵：
[3, 0, 1, 4, 2]
[5, 6, 3, 2, 1]
[1, 2, 0, 1, 5]
[4, 1, 0, 1, 7]
[1, 0, 3, 0, 5]

sumRegion(2, 1, 4, 3) = 8

二维前缀和公式

\text{prefix}[i][j] = \text{matrix}[i-1][j-1] + \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1]

可视化：

计算 prefix[i][j]，需要：
  
  ┌─────┬───┐
  │  A  │ B │  A = prefix[i-1][j-1]
  ├─────┼───┤  B = prefix[i-1][j]
  │  C  │ X │  C = prefix[i][j-1]
  └─────┴───┘  X = matrix[i-1][j-1]

prefix[i][j] = B + C - A + X

为什么减去 A？因为它在 B 和 C 中都被计算了！

查询公式

\text{sum} = \text{prefix}[r2+1][c2+1] - \text{prefix}[r1][c2+1] - \text{prefix}[r2+1][c1] + \text{prefix}[r1][c1]

复杂度：

构建：O(m × n)
查询：O(1)

常见模式与变体

模式 1：计数子数组

模板：

const map = new Map();
map.set(0, 1);  // 总是从基础情况开始！
let count = 0, sum = 0;

for (const num of nums) {
  sum += num;
  const complement = sum - target;
  if (map.has(complement)) count += map.get(complement);
  map.set(sum, (map.get(sum) || 0) + 1);
}

示例：

LC 560：和为 K 的子数组
LC 974：和可被 K 整除的子数组
LC 1074：元素和为目标值的子矩阵数量

模式 2：找最长/最短子数组

模板：

const map = new Map();
map.set(0, -1);  // 存储索引，不是计数！
let maxLen = 0, sum = 0;

for (let i = 0; i < nums.length; i++) {
  sum += transform(nums[i]);  // 如果需要则转换
  
  if (map.has(sum - target)) {
    maxLen = Math.max(maxLen, i - map.get(sum - target));
  }
  
  if (!map.has(sum)) {  // 只存储第一次出现
    map.set(sum, i);
  }
}

示例：

LC 525：连续数组
LC 325：和等于 k 的最长子数组长度
LC 1124：表现良好的最长时间段

模式 3：转换技巧

问题类型	转换	目标
0 和 1 数量相等	0 → -1, 1 → 1	sum = 0
元音/辅音相等	元音 → 1, 辅音 → -1	sum = 0
1 比 0 多	1 → 1, 0 → -1	sum > 0
偶数/奇数频率	偶数 → 0, 奇数 → 1	基于异或

常见陷阱

1. 忘记基础情况

❌ 错误：

const map = new Map();
// 缺少基础情况！

✅ 正确：

const map = new Map();
map.set(0, 1);  // 计数问题
// 或
map.set(0, -1);  // 长度问题

原因：处理从索引 0 开始的子数组！

2. 区间查询的偏移错误

❌ 错误：

function rangeSum(prefix, left, right) {
  return prefix[right] - prefix[left];  // 缺少 +1！
}

✅ 正确：

function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

记住：prefix[i] = 前 i 个元素的和（不包含索引 i）。

3. 负数取模

❌ 错误（在 JavaScript/Java 中）：

let mod = sum % k;  // 可能是负数！
map.set(mod, ...);

✅ 正确：

let mod = sum % k;
if (mod < 0) mod += k;  // 转为正数
map.set(mod, ...);

示例：JS 中 -7 % 5 = -2，但我们需要 3。

4. 长度问题的哈希表值错误

❌ 错误：

map.set(sum, (map.get(sum) || 0) + 1);  // 存储计数！

✅ 正确（长度问题）：

if (!map.has(sum)) {  // 只存第一次出现
  map.set(sum, i);  // 存储索引！
}

原因：找最长子数组时，需要每个和的最早出现位置。

5. 整数溢出

对于非常大的数组，前缀和可能溢出。在 Java 中使用 long，或在 JavaScript 中使用 BigInt（如果需要）。

// Java - 使用 long
long[] prefix = new long[n + 1];

总结

🔑 核心思想

前缀和用 O(n) 预处理换取 O(1) 查询。

构建一次，查询多次！

📋 快速参考

操作	时间	空间
构建前缀和	O(n)	O(n)
区间和查询	O(1)	-
子数组和（哈希表）	O(n)	O(n)
二维构建	O(m×n)	O(m×n)
二维查询	O(1)	-

🎯 模式识别

当看到以下关键词时使用前缀和：

“子数组和等于 k”
“连续数组”
“区间 [i, j] 的和”
对同一数组的多次查询
“和为…的最长/最短子数组”

何时添加哈希表：

查找具有特定和的子数组
计数出现次数
需要跟踪和的历史记录

💡 关键要点

基础情况很重要：总是初始化 map.set(0, ...)
索引 vs 计数：长度问题存索引，频率问题存计数
巧妙转换：将难题转换为 sum = 0
处理负数：某些语言中取模可能是负数
累积思考：前缀和就是累积加法

🚀 面试专业技巧

从简单开始：先实现基础前缀和，然后优化
画出来：画出数组和前缀值
解释数学：详细说明 prefix[r+1] - prefix[l]
考虑空间：能否动态构建前缀和？
测试边界情况：空数组、全是负数、单个元素

🎯 面试模板：当看到”子数组和”时，立即思考：

能用前缀和吗？

需要哈希表吗？

基础情况是什么？

我是要找计数、长度还是索引？

📚 相关主题

滑动窗口：用于不需要前缀和的子数组问题
前缀和上的二分查找：用于”找最小长度”等问题
差分数组：区间更新的逆操作
线段树：当数组可变且需要区间查询时

掌握前缀和，你就能搞定一整类面试题目！🚀