前缀和与差分怎样用？和为 K 的子数组为什么要配哈希表？

简答

前缀和就是提前算好“从开头加到第 i 个数一共是多少”。有了它，任意一段区间的和都能用两个前缀和相减得到，比如 [i, j] 的和等于 prefix[j + 1] - prefix[i]，不用每次重新加一遍。像商品列表里反复问“第 3 到第 8 天的销量合计”，预处理一次 O(n)，之后每次查询 O(1)。

和为 K 的子数组是问有多少段连续子数组的和等于 k。暴力枚举所有区间是 O(n²)。用前缀和换个角度看：以当前位置结尾、和为 k 的区间，就是前面某个前缀和恰好等于“当前前缀和减 k”。所以遍历时用 Map 记录每个前缀和出现了几次，每到一个位置就查一下 sum - k 出现过几次，累加起来，一遍 O(n)。

差分是反过来的操作。要把区间 [l, r] 里的数都加上 v，在差分数组的 l 位置加 v、r + 1 位置减 v，所有修改做完以后求一次前缀和，就得到最终数组。多次区间修改、最后统一查询时很省事。

要注意，Map 要先放一个 0 → 1，代表“一个数都不选”的空前缀，否则从下标 0 开始的区间会漏掉。这题数组里有负数，窗口右扩时和不一定变大，所以不能用滑动窗口。

和为 K 的子数组

先看 prefixSums 怎样求区间和，再看 subarraySum 里先查后存的顺序。

function prefixSums(nums) {
  const prefix = [0];
  for (const num of nums) prefix.push(prefix[prefix.length - 1] + num);
  return prefix;
}

const prefix = prefixSums([3, 1, 4, 1, 5]);
console.log(prefix.join(',')); // 0,3,4,8,9,14
console.log(prefix[4] - prefix[1]); // 6

function subarraySum(nums, k) {
  const count = new Map([[0, 1]]);
  let sum = 0;
  let result = 0;
  for (const num of nums) {
    sum += num;
    result += count.get(sum - k) ?? 0;
    count.set(sum, (count.get(sum) ?? 0) + 1);
  }
  return result;
}

console.log(subarraySum([1, 1, 1], 2)); // 2
console.log(subarraySum([1, 2, 3], 3)); // 2
console.log(subarraySum([1, -1, 0], 0)); // 3
console.log(subarraySum([3, 4, 7, 2, -3, 1, 4, 2], 7)); // 4

prefix 比原数组多一位，prefix[0] 是 0，表示前 0 个数的和。prefix[4] - prefix[1] 是下标 1 到 3 的和，1 + 4 + 1 = 6。多放这个 0，求从开头开始的区间时也能用同一个公式。

subarraySum 里为什么先查 sum - k，再把 sum 存进去？查的是“当前位置之前”的前缀和，如果先存，k 为 0 时当前前缀和会和自己配对，相当于数进了一个空区间。[1, -1, 0] 找和为 0 的区间，答案是 [1, -1]、[0]、[1, -1, 0] 三段，前缀和依次是 1、0、0，第二个 0 能和空前缀的 0 以及第一个 0 各配一次。

为什么不用滑动窗口？滑动窗口要求窗口扩大时和只增不减，缩小时只减不增，这样和太大就缩左边、太小就扩右边。数组里有负数时，这个规律不成立，窗口怎么动都可能错过答案。滑动窗口的写法见《滑动窗口怎样求无重复字符的最长子串？》。

差分：区间修改再统一求值

假设有 5 天的预订记录，每条是“第 l 天到第 r 天，每天多 v 个座位”，最后要求每天一共订了多少。逐天累加是每条 O(区间长度)，用差分每条只改两个位置。

function applyRanges(length, updates) {
  const diff = new Array(length + 1).fill(0);
  for (const [l, r, v] of updates) {
    diff[l] += v;
    diff[r + 1] -= v;
  }
  const result = [];
  let running = 0;
  for (let i = 0; i < length; i++) {
    running += diff[i];
    result.push(running);
  }
  return result;
}

console.log(applyRanges(5, [[0, 1, 10], [1, 2, 20], [1, 4, 25]]).join(',')); // 10,55,45,25,25

差分数组的第 i 位记的是“第 i 天比前一天多了多少”。diff[l] += v 表示从第 l 天开始多出 v，diff[r + 1] -= v 表示从 r + 1 天开始这部分又没了。最后从左往右累加，每天的值就恢复出来了。数组多开一位，是为了 r 等于最后一天时 r + 1 不越界。

常见追问

二维矩阵的区域和怎么用前缀和？

定义 P[i][j] 为左上角到 (i-1, j-1) 这个矩形的和，递推是 P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + matrix[i-1][j-1]。任意子矩形的和用四个前缀和加减得到，同样 O(1)。

和为 K 的子数组如果要求最长的那一段呢？

Map 里不再存次数，改存每个前缀和第一次出现的下标。遇到 sum - k 已经出现过，就用当前下标减去它的第一次下标更新答案。只存第一次出现的位置，才能让区间尽量长。

前缀和数组会不会溢出？

JavaScript 的数字是双精度浮点数，整数在 Number.MAX_SAFE_INTEGER（2⁵³ − 1）以内都是精确的。这题的数据范围远小于这个值。数据很大时可以改用 BigInt。