前缀和算法 是一种通过预处理数组,快速计算任意区间和的技巧。它能在 O(1) 时间复杂度内回答区间和的查询,适用于需要频繁计算子数组/子区间和的问题。以下是其核心应用场景、实现方法及经典例题:
一、适用场景
- 频繁查询区间和
- 多次计算数组的某一子区间
[L, R]
的和。
- 多次计算数组的某一子区间
- 统计满足条件的子数组数量
- 例如“和为k的子数组数量”、“和为偶数的子数组数量”等。
- 处理环形数组或二维矩阵
- 环形数组通过复制数组处理,二维矩阵扩展为二维前缀和。
- 结合哈希表优化查找
- 寻找满足
preSum[j] - preSum[i] = target
的索引组合。
- 寻找满足
二、实现步骤
- 预处理前缀和数组
- 定义
preSum[i]
表示数组前i
项的和(索引通常从1开始)。 - 递推公式:
preSum[i] = preSum[i-1] + nums[i-1]
。
- 定义
- 计算区间和
- 区间
[L, R]
的和为preSum[R+1] - preSum[L]
(左闭右闭区间)。
- 区间
- 结合哈希表优化
- 遍历时记录前缀和出现次数,快速统计满足条件的子数组。
三、经典例题与代码
1. 一维前缀和(区间和查询)
class PrefixSum:def __init__(self, nums):n = len(nums)self.preSum = [0] * (n + 1)for i in range(1, n+1):self.preSum[i] = self.preSum[i-1] + nums[i-1]def query(self, L, R): # 闭区间 [L, R]return self.preSum[R+1] - self.preSum[L]# 示例
nums = [1, 2, 3, 4]
ps = PrefixSum(nums)
print(ps.query(1, 2)) # 输出 2+3=5
2. 统计和为k的子数组数量(哈希优化)
def subarraySum(nums, k):preSum = {0: 1} # 初始前缀和为0出现1次current_sum = 0count = 0for num in nums:current_sum += num# 若 current_sum - target 存在,则存在子数组和为kcount += preSum.get(current_sum - k, 0)preSum[current_sum] = preSum.get(current_sum, 0) + 1return count# 示例
nums = [1, 1, 1]
print(subarraySum(nums, 2)) # 输出 2
3. 二维前缀和(矩阵区域和)
class MatrixPrefixSum:def __init__(self, matrix):m, n = len(matrix), len(matrix[0])self.preSum = [[0]*(n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):self.preSum[i][j] = matrix[i-1][j-1] + self.preSum[i-1][j] + self.preSum[i][j-1] - self.preSum[i-1][j-1]def query(self, x1, y1, x2, y2): # 左上角(x1,y1),右下角(x2,y2)return self.preSum[x2+1][y2+1] - self.preSum[x1][y2+1] - self.preSum[x2+1][y1] + self.preSum[x1][y1]# 示例
matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]
mps = MatrixPrefixSum(matrix)
print(mps.query(1, 1, 2, 2)) # 输出 5+6+8+9=28
四、常见问题与陷阱
- 索引偏移问题
- 前缀和数组通常比原数组多一个元素,需注意索引转换(例如原数组的
nums[i]
对应preSum[i+1]
)。
- 前缀和数组通常比原数组多一个元素,需注意索引转换(例如原数组的
- 负数与哈希表结合
- 当数组中存在负数时,前缀和可能重复,需用哈希表记录所有出现位置。
- 环形数组处理
- 若数组是环形的(如 LeetCode 918),可将原数组复制一份拼接,转化为线性问题。
五、适用问题特征
- 题目中出现 “子数组和”、“连续区间和”、“多次查询区间和” 等关键词。
- 暴力解法时间复杂度为 O(n²),前缀和可优化至 O(n) 或 O(1)。
前缀和是解决子数组/子区间问题的利器,结合哈希表或二分查找可进一步扩展其应用场景。