0 Prefix Sum Basic

0.1 前缀和定义（1-indexed）

  1. 数列前n项和：
  • 1-indexed: $$\text{prefixSum}[i] = \sum_{j=1}^{i} a[j] = a[i] = a[1] + a[2] + \cdots + a[i]$$
  • 0-indexed: $$\text{prefixSum}[i] = \sum_{j=0}^{i-1} a[j] = a[i]= a[0] + a[1] + \cdots + a[i-1]$$
  1. 前缀和分为两类：
类型预处理查询
一维前缀和$O(n)$$O(1)$
二维前缀和$O(nm)$$O(1)$
  • 区间和公式：
    • 1-indexed：$\text{sum(l, r) = prefixSum[r] - prefixSum[l - 1]}$
    • 0-indexed：$\text{sum(l, r) = prefixSum[r + 1] - prefixSum[l]}$
  1. 适用场景:
    • 数组不变(静态),多次查询区间和 → 前缀和
    • 数组会被修改 → 需要树状数组 / 线段树(前缀和不适用)
    • “子数组和满足某条件"的计数问题 → 前缀和 + 哈希表

0.1.1 一维前缀和

区间[l , r]的和：$$\text{sum}(l, r) = S[r] - S[l - 1]$$

  • S[0] = 0 的作用:当 l = 1 时公式仍然成立,无需特判
1# 1-indexed
2# 预处理O(n)
3S = [0] * (n + 1)
4for i in range(1, n + 1):
5	S[i] = S[i - 1] + a[i]
6
7# 查询O(1):[l, r]
8ans = S[r] - S[l - 1]

 1# 构建：prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
 2# 注意 prefix 长度比 nums 多 1，prefix[0] = 0（空前缀）
 3nums   = [2, 3, 1, 4, 5]
 4prefix = [0, 2, 5, 6, 10, 15]
 5#         ^  ^  ^
 6#         |  |  prefix[2] = nums[0]+nums[1] = 5
 7#         |  prefix[1] = nums[0] = 2
 8#         prefix[0] = 0 (空前缀)
 9
10# 查询 nums[l:r] 的和（左闭右开）
11sub_sum = prefix[r] - prefix[l]
12
13# 例：nums[1:4] = [3, 1, 4] 的和 = prefix[4] - prefix[1] = 10 - 2 = 8

代码模板：

 1from itertools import accumulate
 2
 3# 方法一：手动构建
 4prefix = [0]
 5for x in nums:
 6    prefix.append(prefix[-1] + x)
 7
 8# 方法二：用 accumulate（更 Pythonic）
 9prefix = [0] + list(accumulate(nums))
10
11# 查询 [l, r] 闭区间的和
12def range_sum(l, r):
13    return prefix[r + 1] - prefix[l]

0.1.2 二维前缀和

问题是：输入$n \times m$的整数矩阵$A_{n \times m}$多次查询子矩阵元素之和 定义：S[i][j]表示二维数组中，从(1, 1)到$(i, j)$所包围的矩阵元素之和（即左下元素矩形区域之和）

二维前缀和示意图 预处理：容斥原理 $$S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]$$

  • S[i-1][j]:左方大块
  • S[i][j-1]:下方大块
  • 两者重叠了 S[i-1][j-1],减掉一次
  • 最后补上当前元素 a[i][j]

二维前缀和示意图 查询：求以($x_{1}, y_{1}$)为左下角，($x_{2}, y_{2}$)为右上角的矩阵元素之和 $$S_{\text{阴影}} = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$$

  • 从整个右上大块 S[x2][y2] 出发
  • 减去左方多余部分 S[x1-1][y2]
  • 减去下方多余部分 S[x2][y1-1]
  • 上、左两块重叠区域 S[x1-1][y1-1] 被减了两次,加回一次
1# 下标从 1 开始
2S = [[0] * (m + 1) for _ in range(n + 1)]
3for i in range(1, n + 1):
4    for j in range(1, m + 1):
5        S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + a[i][j]
6
7# 查询 (x1, y1) 到 (x2, y2)
8ans = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]

0.1.3 nums 0-indexed or 1-indexed

nums 0-indexed（LeetCode）： nums[0], nums[1], ..., nums[n-1]

1pre[0] = 0
2pre[i] = nums[0] + ... + nums[i-1]
3
4sum(left, right) = pre[right + 1] - pre[left]   # 要 +1

nums 1-indexed（竞赛/伪代码）： nums[1], nums[2], ..., nums[n]

1pre[0] = 0
2pre[i] = nums[1] + ... + nums[i]
3
4sum(left, right) = pre[right] - pre[left - 1]   # 不用 +1

区别就在查询公式:

  • nums 1-indexed：pre[i] 和 nums[i] 天然对齐，pre[i] 就是前 i 个元素的和，公式更直觉
  • nums 0-indexed：有偏移，需要 right + 1 来补

1 前缀和基础模板

1.1 一维前缀和：区域和检索 | Easy

这里我们使用0-indexed：$\text{pre}[i] = a[0] + a[1] + \cdots + a[i - 1], \quad \text{pre}[0] = 0$

查询：$\text{sum(l, r) = pre[r + 1] - pre[l]}$

 1class NumArray:
 2
 3    def __init__(self, nums: List[int]):
 4        self.pre = [0] * (len(nums) + 1)
 5        for i, num in enumerate(nums):
 6            self.pre[i + 1] = self.pre[i] + num
 7        # self.pre = list(accumulate(nums, initial=0))
 8
 9    def sumRange(self, left: int, right: int) -> int:
10        return self.pre[right + 1] - self.pre[left]

1.2 二维前缀和：二维区域和检索 | Easy

pre[i][j] 表示以 (0,0) 到 (i-1,j-1) 为对角的矩形元素和

构建(容斥): $$pre[i+1][j+1] = pre[i+1][j] + pre[i][j+1] - pre[i][j] + matrix[i][j]$$

查询(左下角 (r1,c1),右上角 (r2,c2)): $$\text{sum} = pre[r2+1][c2+1] - pre[r1][c2+1] - pre[r2+1][c1] + pre[r1][c1]$$

 1class NumMatrix:
 2    def __init__(self, matrix: List[List[int]]):
 3        m, n = len(matrix), len(matrix[0])
 4        self.pre = [[0] * (n + 1) for _ in range(m + 1)]
 5        for i in range(m):
 6            for j in range(n):
 7                self.pre[i+1][j+1] = (self.pre[i+1][j] + self.pre[i][j+1]
 8                                      - self.pre[i][j] + matrix[i][j])
 9
10    def sumRegion(self, r1: int, c1: int, r2: int, c2: int) -> int:
11        return (self.pre[r2+1][c2+1] - self.pre[r1][c2+1]
12                - self.pre[r2+1][c1] + self.pre[r1][c1])

2 前缀和 + 哈希表

子数组 [l, r] 的和为 k ⟺ pre[r+1] - pre[l] = k ⟺ pre[l] = pre[r+1] - k

  • 遍历到每个位置时,查询”之前出现过多少个前缀和等于 当前前缀和 - k"
  • 用哈希表 $O(1)$ 查询
题目转化哈希表存什么
560 和为 K 的子数组pre[l] = s - k前缀和 → 出现次数
523 连续的子数组和pre[r] ≡ pre[l] (mod k)余数 → 最早下标
974 和可被 K 整除同上,计数版余数 → 出现次数
525 连续数组把 0 看作 -1,找和为 0 的最长子数组前缀和 → 最早下标
437 路径总和 III树上前缀和,回溯时撤销前缀和 → 出现次数

判断存"次数"还是"下标":

  • 求数量 → 存出现次数
  • 求最长/最短长度 → 存最早/最新出现的下标

2.1 和为 K 的子数组 | Medium

题目：给定整数数组 nums 和一个整数 k ，统计该数组中和为 k 的子数组的个数；子数组是数组中元素的连续非空序列

思路分析:

  • 找一个子数组之和sum(l, r) = k $\Rightarrow$ pre[r + 1] - pre[l] = k $\Rightarrow$ pre[l] = pre[r + 1] - k
  • 哈希表存{前缀和：出现次数}
  • 不能用滑动窗口:数组含负数时窗口和不单调,滑窗失效，这是和"长度最小的子数组"(正数数组)的本质区别

踩坑记录：

  • 初始化：cnt[0] = 1，否则会漏掉从下标0开始自身等于k的子数组
  • 先查询后插入
 1class Solution:
 2    def subarraySum(self, nums: List[int], k: int) -> int:
 3        ans = 0
 4        prefix = 0
 5        cnt = defaultdict(int)
 6        cnt[0] = 1
 7
 8        for num in nums:
 9            prefix += num
10            ans += cnt[prefix - k]
11            cnt[prefix] += 1
12        
13        return ans

复杂度：

  • 时间：O(n)
  • 空间：O(n)

2.2 最大子数组和 | Medium

题目： 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

思路分析:

  • 子数组sum(l, r) = prefix[r + 1] - prefix[l]最大，固定右端点，想让sum最大就需要让prefix[l]最小，即当前前缀和减去历史最小前缀和

踩坑记录： 记住固定右端点

代码：

 1class Solution:
 2    def maxSubArray(self, nums: List[int]) -> int:
 3        ans = float("-inf")
 4        prefix = 0
 5        min_prefix = 0
 6
 7        for num in nums:
 8            prefix += num
 9            ans = max(ans, prefix - min_prefix)
10            min_prefix = min(min_prefix, prefix)
11        
12        return ans

复杂度：

  • 时间：O(n)
  • 空间：O(1)

2.3 连续的子数组和 | Medium

题目： 判断是否存在长度 ≥ 2 的子数组，其和为 k 的倍数

思路分析:

  • 子数组sum(l, r) % k == 0
  • $\Rightarrow$(pre[r + 1] - pre[l]) % k == 0$\Rightarrow$pre[r + 1] % k == pre[l] % k
  • 哈希表存：{余数：最早出现的代表}，找到相同余数时检查长度

证明：

$pre[r + 1] = a \cdot k + r_{1}, \quad pre[l] = b \cdot k + r_{2}$，其中$r_{1} = pre[r + 1] % k, \quad r_2 = pre[l] % k$

$\Rightarrow$:

若$(pre[r +1] - pre[l]) = ck$，则$(a - b)\cdot k + (r_{1} - r_{2}) = c \cdot k$

所以：$r_{1} - r_{2} = (c - a + b) \cdot k$

又因为：$0 \le r_{1}, r_{2} < k$

所以：$|r_{1}- r_{2} | < k$ 即 $r_{1} = r_{2}$

$\Leftarrow$：

若$r_{1} = r_{2}$，$pre[r+1] - pre[l] = (a - b)k$，显然是k的倍数

踩坑记录：

  • 初始化 {0: -1}，-1 代表空前缀的"虚拟下标"，这样 i - (-1) >= 2 即 i >= 1，即从头开始长度至少为 2

代码：

 1class Solution:
 2    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
 3        prefix = 0
 4        remainder_idx = {0:-1}
 5        for i, num in enumerate(nums):
 6            prefix += num
 7            r = prefix % k
 8            if r in remainder_idx:
 9                if i - remainder_idx[r] >= 2:
10                    return  True
11            else:
12                remainder_idx[r] = i
13        return False

复杂度：

  • 时间：O(n)
  • 空间：O(min(n, k))

2.4 和可被 K 整除的子数组 | Medium

题目： 统计和能被 k 整除的子数组个数

思路分析:

  • 子数组sum(l, r) % k == 0 $\Rightarrow$ pre[r] % k == pre[l] % k
  • 哈希表存：{余数：出现次数}

踩坑记录：

  • 负数取模：Python 中 -1 % 5 = 4，天然是非负余数，没问题。但 C++/Java 中 -1 % 5 = -1，需要 ((pre % k) + k) % k 修正

代码：

 1class Solution:
 2    def subarraysDivByK(self, nums: List[int], k: int) -> int:
 3        prefix = 0
 4        cnt = 0
 5        remainder = defaultdict(int)
 6        remainder[0] = 1
 7
 8        for num in nums:
 9            prefix += num
10            r = prefix % k
11            cnt += remainder[r]
12            remainder[r] += 1
13
14        return cnt

复杂度：

  • 时间：O(n)
  • 空间：O(min(n, k))

2.5 连续数组 | Medium

题目： 给定二进制数组，找含相同数量 0 和 1 的最长连续子数组的长度

思路分析:

  • 把0视为-1，问题变成找和为0的最长子数组，pre[l] == pre[r]时sum(l + 1, r) == 0
  • 哈希表存：{前缀和：最早下标}，答案取max(i - earliest_idx)

踩坑记录：

  • 如何转换问题是关键
  • 只存最早的下标

代码：

 1class Solution:
 2    def findMaxLength(self, nums: List[int]) -> int:
 3        prefix = 0
 4        best = 0
 5        first_idx = {0 : -1}
 6
 7        for i, num in enumerate(nums):
 8            prefix += 1 if num == 1 else -1
 9            if prefix in first_idx:
10                best = max(best, i - first_idx[prefix])
11            else:
12                first_idx[prefix] = i
13
14        return best

复杂度：

  • 时间：O(n)
  • 空间：O(n)

2.6 路径总和 | Medium

题目： 给定二叉树和 targetSum，统计路径和等于 targetSum 的路径数（路径方向必须向下）

思路分析：二叉树版本的和为k的子数组

  • 从根节点到当前节点维护前缀和，pre - targetSum在哈希表中出现过几次就有几条路径
  • 哈希表存：{前缀和：出现次数}
  • 回溯时需要撤销，因为不同分支不共享前缀和

踩坑记录：

  • 必须回溯：
  • 和“和为k的子数组”完全一样的初始化：{0:1}
  • 节点值可以为负数，所以不能剪枝

代码：

 1# Definition for a binary tree node.
 2# class TreeNode:
 3#     def __init__(self, val=0, left=None, right=None):
 4#         self.val = val
 5#         self.left = left
 6#         self.right = right
 7class Solution:
 8    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
 9        cnt = defaultdict(int)
10        cnt[0] = 1
11
12        def dfs(node, prefix):
13            if not node:
14                return 0
15            prefix += node.val
16            ans = cnt[prefix - targetSum]
17            cnt[prefix] += 1
18            ans += dfs(node.right, prefix) + dfs(node.left, prefix)
19            cnt[prefix] -= 1
20            return ans
21        
22        return dfs(root, 0)

复杂度：

  • 时间： O(n)，每个节点访问一次
  • 空间： O(n)，递归栈 + 哈希表，最坏都是 O(n)

2.7 前缀和 + 哈希表 总结

模板：

1hashmap = {初始值}   # 哨兵
2pre = 0
3for i, num in enumerate(nums):
4    pre += 转化后的num
5    # 先查：在 hashmap 中找满足条件的 pre[l]
6    # 再存：把当前 pre 存入 hashmap

维度1：匹配条件

  • pre[l] = pre[r] - k：和为k的子数组，路径总和
  • pre[l] % k == pre[r] % k：连续的子数组和，和可被 K 整除的子数组
  • pre[l] == pre[r](k = 0)：连续数组

维度2：哈希表存什么

  • 计数：{key: 出现次数}，初始化：{0: 1}
  • 最长长度/是否存在：{key: 最早下标}，初始化：{0: -1}
  • 不管存次数还是存下标，哨兵都是在处理"从数组头开始的子数组"：
    • {0: 1}：空前缀本身算一次出现，这样如果 pre[r] 自身就满足条件，能被统计到
    • {0: -1}：空前缀的"虚拟下标"是 -1，这样 i - (-1) 就是从头到 i 的长度

3 变形：前缀积

3.1 除自身以外数组的乘积 | Medium

题目： 给定整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。约束：

  • 不能使用除法
  • 时间复杂度必须为 O(n)

思路分析:

  • 除自身以外的乘积 = 左边所有数的积 × 右边所有数的积：

$$answer[i] = \text{pre}[i] \times \text{suf}[i]$$

$$\text{其中 } \text{pre}[i] = \prod_{j=0}^{i-1} nums[j], \quad \text{suf}[i] = \prod_{j=i+1}^{n-1} nums[j]$$

1answer[i] = (nums[0] ... nums[i - 1]) * (nums[i + 1] ... nums[n - 1])
2          = preLeft[i] * sufRight[i]

与前缀和的对应关系:

  • 加法的单位元是 0 → 前缀和哨兵 pre[0] = 0
  • 乘法的单位元是 1 → 前缀积哨兵 pre[0] = 1（左边没有数时为空积）

plan 1：显式前缀积 + 后缀积数组

1pre[i] = nums[0] · ... · nums[i-1]   （左边的积）
2suf[i] = nums[i+1] · ... · nums[n-1] （右边的积）
3answer[i] = pre[i] * suf[i]

以 nums = [1, 2, 3, 4] 为例：

pre = [1, 1, 2, 6]
suf = [24, 12, 4, 1]
ans = [24, 12, 8, 6]

plan 2：空间优化（滚动后缀积）

  • pre 数组可以直接填进 answer，不需要单独保留，每个位置再去单独乘suf就是answer
  • 如何去算suf呢？最后一位suf等于1，从右往左算suf *= nums[i]，再去乘对应位置的ans/pre
第一遍(从左到右):  answer[i] = nums[0]·...·nums[i-1]
第二遍(从右到左):  answer[i] *= suf, 然后 suf *= nums[i]

踩坑记录：

  • 第二遍两行顺序不能反，必须先用再更新：answer[i] *= suf 在前，suf *= nums[i] 在后。 反了会把 nums[i] 自己乘进去，违反"除自身以外"
  • 不能用除法本质原因是数组可能含 0：含一个 0 → 总积 / 0 直接崩
  • 哨兵初始化 answer[0] = 1 和 suf = 1，都是"空积 = 乘法单位元"。 类比前缀和的 pre[0] = 0，不要习惯性写成 0。

代码： plan 1：显式前缀积 + 后缀积数组

 1class Solution:
 2    def productExceptSelf(self, nums: List[int]) -> List[int]:
 3        n = len(nums)
 4        pre = [1] * n    # pre[i] = 左边所有数的积
 5        suf = [1] * n    # suf[i] = 右边所有数的积
 6
 7        for i in range(1, n):
 8            pre[i] = pre[i - 1] * nums[i - 1]
 9
10        for i in range(n - 2, -1, -1):
11            suf[i] = suf[i + 1] * nums[i + 1]
12
13        return [pre[i] * suf[i] for i in range(n)]

复杂度:

  • 时间O(n)：三次遍历
  • 空间O(n)：两个额外数组

plan 2：空间优化（滚动后缀积）

 1class Solution:
 2    def productExceptSelf(self, nums: List[int]) -> List[int]:
 3        n = len(nums)
 4        answer = [1] * n
 5
 6        for i in range(1, n):
 7            answer[i] = answer[i - 1] * nums[i - 1]
 8
 9        suffix = 1
10        for i in range(n - 1, -1, -1):
11            answer[i] *= suffix
12            suffix *= nums[i]
13
14        return answer

复杂度：

  • 时间 O(n)：两次遍历
  • 空间 O(1)：输出数组不计入额外空间（题目明确说明），只用了 suf 一个变量