001 - 前缀和算法：从原理到实战，一文讲透区间和问题

📖 摘要

前缀和（Prefix Sum）是算法竞赛和面试中的高频考点，能将区间和查询从O(n)优化到O(1)，还能结合哈希表高效统计满足条件的子数组。本文将深入浅出讲解前缀和的核心思想、应用场景，并通过LeetCode经典题目带你彻底掌握这一算法技巧！

📚 目录

1. 什么是前缀和？
2. 前缀和的应用场景
3. 一维前缀和经典例题
4. 二维前缀和与矩阵查询
5. 前缀和+哈希表的组合技
6. 实战技巧与总结

1. 什么是前缀和？

1.1 一维前缀和

前缀和数组 prefix 的每个元素表示原数组前 i 项的和：
$$prefix[i]=nums[0]+nums[1]+\cdots +nums[i-1]$$
区间和计算：
若求原数组区间 [L, R] 的和，只需：
$$sum=prefix[R+1]-prefix[L]$$
示例：
原数组 [2, 3, -1, 4] 的前缀和为 [0, 2, 5, 4, 8]，区间 [1,3] 的和为 8 - 2 = 6。

1.2 二维前缀和

二维前缀和 prefix[i][j] 表示从 (0,0) 到 (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]$$

2. 前缀和的应用场景

• 高频查询区间和
• 统计满足条件的子数组数量（如和为K、可被K整除的子数组）
• 处理含负数的数组或需要取模的场景
• 优化动态规划问题中的重复计算

3. 一维前缀和经典例题

例题1：和为K的子数组

问题：统计数组中连续子数组和为k的数量。
关键思路：

• 用哈希表记录前缀和出现的次数
• 遍历时若发现 sum - k 在哈希表中，则累加次数

代码实现：

def subarraySum(nums, k):
    prefix = {0: 1}  # 初始化：前缀和为0出现1次（空数组）
    sum_, count = 0, 0
    for num in nums:
        sum_ += num
        count += prefix.get(sum_ - k, 0)  # 累加符合条件的子数组数量
        prefix[sum_] = prefix.get(sum_, 0) + 1  # 更新哈希表
    return count

例题2：和可被 K 整除的子数组

关键点：

• 计算前缀和模 K 的余数，利用同余定理
• 处理负数余数：mod = (sum_ % K + K) % K

代码实现：

def subarraysDivByK(nums, K):
    prefix = {0: 1}
    sum_, ans = 0, 0
    for num in nums:
        sum_ += num
        mod = (sum_ % K + K) % K  # 修正负数余数
        ans += prefix.get(mod, 0)
        prefix[mod] = prefix.get(mod, 0) + 1
    return ans

4. 二维前缀和与矩阵查询

例题3：二维区域和检索

核心思想：

• 构建二维前缀和数组时，利用容斥原理：
  $$prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+matrix[i-1][j-1]$$

代码实现：

class NumMatrix:
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                self.prefix[i+1][j+1] = self.prefix[i+1][j] + self.prefix[i][j+1] - self.prefix[i][j] + matrix[i][j]
    
    def sumRegion(self, r1, c1, r2, c2):
        return self.prefix[r2+1][c2+1] - self.prefix[r1][c2+1] - self.prefix[r2+1][c1] + self.prefix[r1][c1]

5. 前缀和+哈希表的组合技

例题4：连续数组

问题：找到含有相同数量0和1的最长子数组。
转化技巧：将0视为-1，问题转化为求和为0的最长子数组。

代码实现：

def findMaxLength(nums):
    prefix = {0: -1}  # 记录前缀和首次出现的下标
    sum_, max_len = 0, 0
    for i, num in enumerate(nums):
        sum_ += 1 if num == 1 else -1
        if sum_ in prefix:
            max_len = max(max_len, i - prefix[sum_])
        else:
            prefix[sum_] = i
    return max_len

6. 实战技巧与总结

✅ 技巧清单

1. 哈希表初始化：通常需加入 {0:1} 或 {0:-1} 处理边界条件
2. 负数取模：使用 (sum % K + K) % K 修正余数
3. 二维前缀和公式：构建时注意容斥，查询时推导区域和公式
4. 空间优化：二维前缀和可覆盖原数组（若允许修改）

🌟 总结

前缀和的核心是空间换时间，通过预处理数组优化区间查询。结合哈希表后，能高效解决子数组统计问题，尤其在处理负数、取模时展现强大能力。掌握前缀和，轻松应对LeetCode中80%的区间和问题！

练习

统计「优美子数组」

💬 互动

你在刷题时遇到过哪些前缀和相关的难题？欢迎留言讨论！
觉得本文有帮助？点赞⭐收藏🔖关注，支持作者持续创作！