算法篇 ｜ 前缀和

前言

在上一章中，我们学习了二分法——通过每次缩小一半搜索范围来高效定位目标。这一章我们来聊另一个同样高效但经常被忽视的技巧：前缀和（Prefix Sum）。

前缀和解决的核心问题是：如何快速求出数组中任意一段连续区间的和？

暴力做法是每次查询都从头加到尾，时间复杂度 O(n)。如果有 m 次查询，总复杂度就是 O(m * n)。而前缀和通过一次 O(n) 的预处理，可以把每次查询降到 O(1)。

这个思想不仅用在算法竞赛中，在前端开发中也有实际应用场景——比如虚拟列表的行高累加、表格区域求和、数据可视化中的区间统计等。在面试中，前缀和更是”和为 K 的子数组”这类高频题的标准解法。

本章我们会依次讲解：一维前缀和、差分数组、二维前缀和，并通过经典 LeetCode 题目帮你建立清晰的思维模型。

诊断自测

Q1：给定数组 [1, 2, 3, 4, 5]，如何 O(1) 时间求出下标 1 到 3（即 2 + 3 + 4 = 9）的区间和？

Q2：给定数组和一个整数 k，找出数组中和为 k 的连续子数组的个数。你的思路是什么？

Q3：对数组的某个区间 [l, r] 内的所有元素加上一个值 d，如何高效处理多次这样的操作？

一、一维前缀和

1.1 基本概念

给定一个数组 nums，它的前缀和数组 prefix 定义为：

prefix[0] = 0
prefix[i] = nums[0] + nums[1] + ... + nums[i-1]

也就是说，prefix[i] 表示原数组前 i 个元素的和。

有了前缀和数组，任意区间 [i, j] 的和就可以用减法算出来：

sum(i, j) = prefix[j + 1] - prefix[i]

1.2 构建前缀和

function buildPrefixSum(nums) {
  const prefix = new Array(nums.length + 1).fill(0);

  for (let i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }

  return prefix;
}

// 示例
const nums = [1, 2, 3, 4, 5];
const prefix = buildPrefixSum(nums);
// prefix = [0, 1, 3, 6, 10, 15]

// 求区间 [1, 3] 的和（即 2 + 3 + 4）
const rangeSum = prefix[4] - prefix[1]; // 10 - 1 = 9

为什么 prefix 的长度是 nums.length + 1？

因为我们需要 prefix[0] = 0 来处理从下标 0 开始的区间。如果不加这个哨兵值，计算 sum(0, j) 时就需要单独处理，代码会变得复杂。

1.3 经典题：区域和检索 - 数组不可变（LeetCode 303）

给定一个整数数组 nums，实现 NumArray 类，支持多次查询区间 [left, right] 的和。

class NumArray {
  constructor(nums) {
    // 预处理：构建前缀和数组
    this.prefix = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) {
      this.prefix[i + 1] = this.prefix[i] + nums[i];
    }
  }

  sumRange(left, right) {
    return this.prefix[right + 1] - this.prefix[left];
  }
}

// 使用示例
const numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // 1（即 -2 + 0 + 3）
numArray.sumRange(2, 5); // -1（即 3 + -5 + 2 + -1）
numArray.sumRange(0, 5); // -3

复杂度分析：

• 预处理：O(n) 时间，O(n) 空间
• 每次查询：O(1) 时间

1.4 经典题：和为 K 的子数组（LeetCode 560）

给定一个整数数组 nums 和一个整数 k，统计并返回该数组中和为 k 的连续子数组的个数。

这是前缀和最经典的应用题之一，也是面试高频题。

暴力思路：枚举所有子数组，计算每个子数组的和，O(n²) 或 O(n³)。

前缀和 + 哈希表思路：

核心洞察：如果 prefix[j] - prefix[i] === k，则子数组 nums[i..j-1] 的和为 k。

换个角度：当我们遍历到位置 j 时，当前前缀和为 prefix[j]，我们需要找之前有多少个位置 i 满足 prefix[i] === prefix[j] - k。

这不就是”两数之和”的变形吗？用哈希表记录每个前缀和出现的次数！

function subarraySum(nums, k) {
  const map = new Map();
  map.set(0, 1); // 前缀和为 0 出现了 1 次（空前缀）

  let sum = 0;  // 当前前缀和
  let count = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];

    // 检查是否存在前缀和为 sum - k 的位置
    if (map.has(sum - k)) {
      count += map.get(sum - k);
    }

    // 更新哈希表
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  return count;
}

为什么初始化 map.set(0, 1)？

因为当 sum === k 时，sum - k === 0，这意味着从数组开头到当前位置的子数组和恰好为 k。如果不初始化 map.set(0, 1)，这种情况就会被遗漏。

复杂度分析：

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

二、差分数组

差分数组可以看作前缀和的”逆运算”。前缀和是把求区间和变成 O(1)，差分数组是把区间修改变成 O(1)。

2.1 基本概念

给定数组 nums，它的差分数组 diff 定义为：

diff[0] = nums[0]
diff[i] = nums[i] - nums[i-1]  (i > 0)

差分数组有一个关键性质：对差分数组求前缀和，可以还原出原数组。

更重要的是：如果我们要对原数组的区间 [l, r] 内所有元素都加上 d，在差分数组上只需要：

diff[l] += d
diff[r + 1] -= d  // 如果 r + 1 < nums.length

2.2 差分数组的实现

// 构建差分数组
function buildDiff(nums) {
  const diff = new Array(nums.length).fill(0);
  diff[0] = nums[0];
  for (let i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
  }
  return diff;
}

// 区间加操作
function rangeAdd(diff, l, r, d) {
  diff[l] += d;
  if (r + 1 < diff.length) {
    diff[r + 1] -= d;
  }
}

// 从差分数组还原原数组
function restore(diff) {
  const result = new Array(diff.length);
  result[0] = diff[0];
  for (let i = 1; i < diff.length; i++) {
    result[i] = result[i - 1] + diff[i];
  }
  return result;
}

2.3 实际应用场景

差分数组在前端中也有应用场景，比如：

• 日历中标记多个时间区间”是否忙碌”
• 批量处理表格中某些行/列的增减操作
• 航班预订统计（LeetCode 1109）

// 示例：航班预订统计
// bookings[i] = [first, last, seats] 表示从第 first 到第 last 航班预订了 seats 个座位
function corpFlightBookings(bookings, n) {
  const diff = new Array(n).fill(0);

  for (const [first, last, seats] of bookings) {
    diff[first - 1] += seats;       // 1-indexed 转 0-indexed
    if (last < n) {
      diff[last] -= seats;
    }
  }

  // 还原：对差分数组求前缀和
  const result = new Array(n);
  result[0] = diff[0];
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] + diff[i];
  }

  return result;
}

复杂度分析：

• m 次区间操作：O(m)（每次 O(1)）
• 最终还原：O(n)
• 总复杂度：O(m + n)，远优于暴力的 O(m * n)

三、二维前缀和

3.1 基本概念

一维前缀和处理的是”区间”查询，二维前缀和处理的是”矩形区域”查询。

给定一个二维矩阵 matrix，其二维前缀和 prefix[i][j] 表示从 (0, 0) 到 (i-1, j-1) 这个矩形区域内所有元素的和。

构建公式（容斥原理）：

prefix[i][j] = matrix[i-1][j-1]
             + prefix[i-1][j]
             + prefix[i][j-1]
             - prefix[i-1][j-1]

查询 (r1, c1) 到 (r2, c2) 矩形区域的和：

sum = prefix[r2+1][c2+1]
    - prefix[r1][c2+1]
    - prefix[r2+1][c1]
    + prefix[r1][c1]

3.2 经典题：二维区域和检索（LeetCode 304）

给定一个二维矩阵 matrix，实现 NumMatrix 类，支持查询子矩形区域的元素总和。

class NumMatrix {
  constructor(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;

    // 构建二维前缀和，大小为 (m+1) x (n+1)
    this.prefix = Array.from({ length: m + 1 }, () =>
      new Array(n + 1).fill(0)
    );

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        this.prefix[i][j] =
          matrix[i - 1][j - 1] +
          this.prefix[i - 1][j] +
          this.prefix[i][j - 1] -
          this.prefix[i - 1][j - 1];
      }
    }
  }

  sumRegion(row1, col1, row2, col2) {
    return (
      this.prefix[row2 + 1][col2 + 1] -
      this.prefix[row1][col2 + 1] -
      this.prefix[row2 + 1][col1] +
      this.prefix[row1][col1]
    );
  }
}

理解容斥原理的关键：画个图就明白了。查询区域 = 大矩形 - 上方矩形 - 左方矩形 + 左上角矩形（因为被减了两次，要加回来）。

复杂度分析：

• 预处理：O(m * n) 时间和空间
• 每次查询：O(1) 时间

四、前缀和 + 哈希表：一个强大的组合

前缀和最强大的用法，不是单独使用，而是和哈希表结合。这个组合能解决一大类”满足某种条件的子数组”问题。

通用模式：

1. 维护当前前缀和 sum
2. 用哈希表记录之前所有前缀和（及其出现次数/位置）
3. 对于当前的 sum，在哈希表中查找 sum - target

这个模式的变体可以解决：

• 和为 K 的子数组（前面已讲）
• 和可被 K 整除的子数组：把前缀和换成前缀和对 K 取模
• 连续子数组和（LeetCode 523）：前缀和取模 + 记录最早出现的位置
• 0 和 1 个数相同的最长子数组：把 0 看成 -1，转化为和为 0 的最长子数组

// 示例：和可被 K 整除的子数组数量（LeetCode 974）
function subarraysDivByK(nums, k) {
  const map = new Map();
  map.set(0, 1);

  let sum = 0;
  let count = 0;

  for (const num of nums) {
    sum += num;
    // 处理负数取模的问题
    const mod = ((sum % k) + k) % k;

    if (map.has(mod)) {
      count += map.get(mod);
    }
    map.set(mod, (map.get(mod) || 0) + 1);
  }

  return count;
}

注意 JavaScript 的取模运算：-1 % 5 在 JS 中结果是 -1 而不是 4。处理负数取模时，需要用 ((n % k) + k) % k 来得到正确的非负余数。

常见误区

误区一：“前缀和数组的长度和原数组一样”

正确的前缀和数组长度应该是 nums.length + 1，第一个元素为 0。这样 prefix[i] 表示前 i 个元素的和，区间 [i, j] 的和就是 prefix[j+1] - prefix[i]。如果长度和原数组一样，处理”从下标 0 开始”的区间就需要特殊处理。

误区二：“前缀和只能处理求和”

前缀和的思想可以推广到任何满足结合律和可逆运算的操作。比如：前缀异或可以快速求区间异或值，前缀积（如果不含零）可以求区间积。核心思想是一样的：通过预处理，把区间查询转化为两个端点的运算。

误区三：“差分数组就是前缀和数组”

它们是逆运算关系。对原数组求前缀和得到前缀和数组；对原数组求差分得到差分数组。前缀和用于加速”区间查询”，差分数组用于加速”区间修改”。两者的应用场景完全不同。

误区四：“和为 K 的子数组可以用滑动窗口”

这是一个常见的误判。滑动窗口要求窗口的扩大和缩小有单调性——当窗口和增大时，收缩窗口可以减小和。但如果数组中包含负数，这个单调性就不成立了。“和为 K 的子数组”允许负数，所以必须用前缀和 + 哈希表，而不是滑动窗口。

小结

前缀和是一种”以空间换时间”的预处理思想，它的核心价值在于：把重复的区间求和操作，提前算好并缓存起来。

核心要点

1. 一维前缀和：prefix[i] 表示前 i 个元素的和，区间查询 O(1)
2. 差分数组：前缀和的逆运算，用于 O(1) 的区间修改
3. 二维前缀和：基于容斥原理，处理矩形区域查询
4. 前缀和 + 哈希表：解决”和为 K 的子数组”这类问题的标准组合
5. 初始化 map.set(0, 1)：处理从头开始的子数组，别忘了这一步

本章思维导图

练习挑战

第一题 ⭐：区间求和（基础）

给定数组 nums = [3, 1, 4, 1, 5, 9, 2, 6]，请构建前缀和数组，并回答：区间 [2, 5] 的和是多少？

const nums = [3, 1, 4, 1, 5, 9, 2, 6];
const prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31];

// 区间 [2, 5] 的和 = prefix[6] - prefix[2] = 23 - 4 = 19
// 即 4 + 1 + 5 + 9 = 19

第二题 ⭐⭐：连续子数组和（LeetCode 523）

给定一个整数数组 nums 和一个整数 k，如果存在一个长度至少为 2 的连续子数组，其元素总和为 k 的倍数，返回 true。

function checkSubarraySum(nums, k) {
  const map = new Map();
  map.set(0, -1); // 前缀和取模为 0 出现在位置 -1（表示开头之前）

  let sum = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    const mod = k === 0 ? sum : ((sum % k) + k) % k;

    if (map.has(mod)) {
      // 子数组长度至少为 2
      if (i - map.get(mod) >= 2) {
        return true;
      }
    } else {
      map.set(mod, i); // 只记录最早出现的位置
    }
  }

  return false;
}

第三题 ⭐⭐⭐：除自身以外数组的乘积（LeetCode 238）

给定数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。要求 O(n) 时间且不能使用除法。

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);

  // 第一遍：从左到右，计算每个位置左边所有元素的乘积
  let leftProduct = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = leftProduct;
    leftProduct *= nums[i];
  }

  // 第二遍：从右到左，乘上每个位置右边所有元素的乘积
  let rightProduct = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= rightProduct;
    rightProduct *= nums[i];
  }

  return answer;
}

自我检测

• 能手写一维前缀和的构建代码，并解释为什么 prefix 长度是 n + 1
• 能用前缀和数组 O(1) 查询任意区间的和
• 能说清楚差分数组的定义，以及它和前缀和的逆运算关系
• 能用差分数组实现 O(1) 的区间加操作
• 能解释二维前缀和的容斥原理，并手写构建和查询代码
• 能用前缀和 + 哈希表解决”和为 K 的子数组”，并解释 map.set(0, 1) 的作用
• 能判断一道题应该用前缀和还是滑动窗口（关键：数组是否含负数）
• 能说出 JavaScript 中负数取模的坑及其解决方案 ((n % k) + k) % k