08 · 前缀和

目标：理解 prefix[i] 含义，会用前缀和 O(1) 求区间和；掌握「和为 k」的哈希套路。
精讲 303、560。

1. 为什么面试考

• 区间求和是数组基础题；前缀和把多次查询从 O(n) 降到 O(1)。
• 560 和为 K 的子数组 是「前缀和 + 哈希」代表作，Medium 高频。
• 考你能不能写出 prefix[j] - prefix[i] = k 这个等式。

2. 零基础概念

前缀和数组 prefix：

nums:   [1, 2, 3, 4]
prefix: [0, 1, 3, 6, 10]
         ↑
    prefix[0]=0 方便算

定义：

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

区间和 [left, right]（闭区间）：

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

例子：nums[1..2] = 2+3 = 5 → prefix[3] - prefix[1] = 6 - 1 = 5。

一维前缀和适用：

场景	做法
多次问区间和	预处理 prefix，每次 O(1)
子数组和 = k	遍历时找 prefix[j] - k 出现过几次

3. JS 模板

3.1 构建前缀和

function buildPrefix(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
}

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

3.2 和为 k 的子数组个数（哈希）

function subarraySum(nums, k) {
  const count = new Map()
  count.set(0, 1) // 空前缀
  let sum = 0
  let ans = 0

  for (const x of nums) {
    sum += x
    ans += count.get(sum - k) || 0
    count.set(sum, (count.get(sum) || 0) + 1)
  }

  return ans
}

核心等式：若 sum[j] - sum[i] = k，则 [i, j) 这一段和为 k。

---

4. 精讲 · 303 区域和检索（数组不可变）

题意：多次查询 [left, right] 区间和。

套路：构造 prefix，查询 O(1)。

/**
 * @param {number[]} nums
 */
var NumArray = function (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]
  }
}

/**
 * @param {number} left
 * @param {number} right
 * @return {number}
 */
NumArray.prototype.sumRange = function (left, right) {
  return this.prefix[right + 1] - this.prefix[left]
}

边界：left === right 时仍成立 → prefix[left+1] - prefix[left] = nums[left]。

---

5. 精讲 · 560 和为 K 的子数组

题意：统计连续子数组和等于 k 的个数。

套路：边遍历边累加 sum；看 sum - k 在之前出现过几次。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  const count = new Map()
  count.set(0, 1)
  let sum = 0
  let ans = 0

  for (const x of nums) {
    sum += x
    ans += count.get(sum - k) || 0
    count.set(sum, (count.get(sum) || 0) + 1)
  }

  return ans
}

为什么 count.set(0, 1)？
表示「还没选任何元素」时前缀和为 0。若某个 sum === k，则 sum - k = 0 应计 1 次——对应从开头开始的子数组。

走一遍 nums = [1,1,1], k = 2：

x	sum	找 sum-k	ans
1	1	0→1	1
1	2	1→1	2
1	3	1→1	3

复杂度：O(n) 时间，O(n) 空间（哈希存前缀和频次）。

---

6. 前缀和 vs 滑动窗口

	前缀和 + 哈希	滑动窗口
数组元素	可正可负	常要求非负（或单调）
问法	和 = k、个数	最长 / 最短子数组
560	✅	❌ 有负数时窗口失效
209	可转化	✅ 更直观

---

7. 练习清单

题号	名称	难度	备注
303	区域和检索	Easy	本篇已精讲
560	和为 K 的子数组	Medium	本篇已精讲
724	寻找数组中心下标	Easy	prefix 左和 = 右和
974	和可被 K 整除的子数组	Medium	(sum-k)%K 同余
525	连续数组	Medium	前缀和 + 哈希，0/1 转化

8. 今日验收

• [ ] 能写出 prefix[i+1] = prefix[i] + nums[i]
• [ ] 能口述区间和公式 prefix[right+1] - prefix[left]
• [ ] 能解释 560 为何初始化 count.set(0, 1)
• [ ] LeetCode 提交 303、560 至少各 1 次 AC

9. 可选 · 记忆唤醒

prefix[0]=0
区间 [L,R] 和 = prefix[R+1] - prefix[L]
560：Map 存前缀和频次，ans += count.get(sum-k)
别忘了空前缀 count.set(0,1)

下一步

→ 09 · 哈希表进阶