前缀和 + 差分数组 + HashMap——秒杀数组子段问题的底层思维

大熊计算机

发布于 2025-07-15 08:42:15

16600

代码可运行

文章被收录于专栏：C博文C博文

运行总次数：0

代码可运行

在算法实战中，数组子段问题（如区间求和、计数、最值等）是高频且核心的挑战。很多开发者面对这类问题本能地想到暴力解法，导致代码在规模数据面前崩溃。本文将揭示一套由前缀和、差分数组和HashMap组成的底层思维框架，结合实战案例与数学推导，展示如何高效秒杀复杂子段问题。

一、前缀和：空间换时间的查询

核心思想：预处理数组，存储前 i 个元素的和 prefix[i]。任意区间 [L, R] 的和可瞬间计算为 prefix[R+1] - prefix[L]，将 O(n) 查询优化至 O(1)。

数学本质：设原数组为 A[0..n-1]，前缀和数组 P 满足：

P[0] = 0  
P[i] = A[0] + A[1] + ... + A[i-1] (i ≥ 1)

则区间和：

sum(L, R) = P[R+1] - P[L]

实战案例1：区间求和 问题：给定数组，多次查询 [L, R] 的和。

class PrefixSum:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i+1] = self.prefix[i] + nums[i]
    
    def query_range(self, L, R):
        return self.prefix[R+1] - self.prefix[L]

# 测试
nums = [1, 3, -2, 4, 5]
ps = PrefixSum(nums)
print(ps.query_range(1, 3))  # 输出: 3 + (-2) + 4 = 5

性能对比：

暴力法：每次查询 O(n)，m 次查询 → O(mn)
前缀和：预处理 O(n)，查询 O(1)，总复杂度 O(n + m) 当 m=100,000, n=100,000 时，暴力法超时（>10s），前缀和仅需 0.1s。

二、HashMap：降维打击子段条件问题

前缀和解决了求和问题，但如何高效寻找满足特定条件的子段（如“和为K”、“0和1数量相等”）？HashMap 通过存储前缀状态实现降维优化。

问题升级：和为K的子数组数量 问题：给定数组 nums 和整数 k，计算和为 k 的连续子数组个数。

暴力陷阱：双重循环枚举所有子数组 → O(n²)，n=10⁵ 时超时。

HashMap优化思路：

计算前缀和 prefix_sum
在遍历时，检查 prefix_sum - k 是否在 HashMap 中出现过
若有，则说明存在子段和为 k

数学推导：设存在 j < i 使得：

prefix[i] - prefix[j] = k  
⇒ prefix[j] = prefix[i] - k

因此，prefix[j] 的出现次数即是以 i 结尾的、和为 k 的子数组数量。

代码实现：

def subarray_sum(nums, k):
    prefix_sum = 0
    count = 0
    sum_count = {0: 1}  # 初始化：前缀和为0出现1次
    
    for num in nums:
        prefix_sum += num
        # 查找是否存在前缀和等于 prefix_sum - k
        count += sum_count.get(prefix_sum - k, 0)
        # 更新当前前缀和出现次数
        sum_count[prefix_sum] = sum_count.get(prefix_sum, 0) + 1
    return count

# 测试
nums = [3, 4, 7, 2, -3, 1, 4, 2]
k = 7
print(subarray_sum(nums, k))  # 输出: 4 (子数组：[3,4], [7], [7,2,-3,1], [1,4,2])

复杂度：时间 O(n)，空间 O(n) 为何高效：HashMap 将二维搜索（枚举起点终点）压缩为一维遍历，利用哈希查找 O(1) 特性。

三、差分数组：区间更新

当问题涉及频繁区间修改（如区间内所有元素加一个值）时，差分数组是比线段树、树状数组更轻量的解决方案。

核心思想：差分数组 diff 满足：

diff[0] = arr[0]
diff[i] = arr[i] - arr[i-1] (i ≥ 1)

对原数组区间 [L, R] 加 val 的操作，转化为：

diff[L] += val
diff[R+1] -= val  (若 R+1 在范围内)

最后通过前缀和还原修改后的数组。

数学证明：还原操作 arr[i] = diff[0] + diff[1] + ... + diff[i] 本质是前缀和。区间 [L, R] 加 val 后，对还原值的影响：

当 i < L：无影响
当 L ≤ i ≤ R：累加了 val
当 i > R：diff[R+1] -= val 抵消多余影响

实战案例：航班预订统计 问题：有 n 个航班，预订记录 bookings = [start, end, seats]，求每个航班的最终预订数。

def corp_flight_bookings(bookings, n):
    diff = [0] * (n + 2)  # 多开空间避免越界
    
    for start, end, seats in bookings:
        diff[start] += seats
        diff[end + 1] -= seats  # 关键操作
    
    # 通过前缀和还原数组
    res = [0] * n
    res[0] = diff[1]
    for i in range(1, n):
        res[i] = res[i-1] + diff[i+1]
    return res

# 测试
bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]]
n = 5
print(corp_flight_bookings(bookings, n)) 
# 输出: [10, 55, 45, 25, 25]

性能优势：

暴力法：每次操作 O(n)，k 次操作 → O(kn)
差分法：每次操作 O(1)，还原 O(n)，总复杂度 O(k + n) 当 k=100,000, n=100,000 时，差分法比暴力法快 1000 倍以上。

四、组合拳实战：二维问题

复杂问题：元素和为目标值的子矩阵数量 问题：给定矩阵 matrix 和目标值 target，计算元素和等于 target 的子矩阵数量。

暴力解法：枚举左上角和右下角 → O(n²m²) → 绝对超时。

降维策略：

固定上下边界，将二维压缩为一维
对每一列计算列前缀和
问题转化为一维数组的“和为 target 的子数组”问题 → 使用HashMap！

代码实现：

def num_submatrix_sum_target(matrix, target):
    rows, cols = len(matrix), len(matrix[0])
    count = 0
    
    # 预处理列方向前缀和
    col_prefix = [[0] * cols for _ in range(rows+1)]
    for i in range(rows):
        for j in range(cols):
            col_prefix[i+1][j] = col_prefix[i][j] + matrix[i][j]
    
    # 固定上下边界
    for top in range(rows):
        for bottom in range(top, rows):
            # 当前上下边界间的列和 → 一维数组
            col_sum = [0] * cols
            for j in range(cols):
                col_sum[j] = col_prefix[bottom+1][j] - col_prefix[top][j]
            
            # 在一维数组上使用HashMap技巧
            prefix_sum = 0
            sum_map = {0: 1}
            for s in col_sum:
                prefix_sum += s
                count += sum_map.get(prefix_sum - target, 0)
                sum_map[prefix_sum] = sum_map.get(prefix_sum, 0) + 1
    return count

# 测试
matrix = [[0,1,0],[1,1,1],[0,1,0]]
target = 0
print(num_submatrix_sum_target(matrix, target))  # 输出: 4

关键洞察：

二维问题通过固定边界降为一维
列前缀和避免重复计算
HashMap 处理一维子数组和

五、思维框架总结

问题分类决策树：

复杂度对比表：问题类型暴力解法优化方案加速比静态区间求和O(n) per query前缀和 O(1) per query10⁶倍 (n=10⁶)子段和为K计数O(n²)前缀和+HashMap O(n)1000倍 (n=10⁴)区间批量增减O(n) per update差分数组 O(1) per update1000倍 (k=10⁵)二维子矩阵和等于targetO(n²m²)降维+HashMap O(n²m)100倍 (n=m=100)
避坑指南：
- 前缀和数组长度应为 n+1，避免边界判断错误
- HashMap 初始需放入 {0: 1}，处理从0开始的子数组
- 差分数组修改后必须用前缀和还原

为什么这些方法有效？

前缀和：本质是积分思想的离散化。将累加操作转化为边界值减法，用预处理空间换取查询时间。
HashMap优化：核心是状态记忆。 prefix_sum - k 的查找等价于寻找历史状态，将双重循环解耦。
差分数组：体现了微分与积分的对称性。修改操作转化为边界微分变化，积分（前缀和）还原整体状态。
复杂度本质：
- 前缀和：空间换时间（O(n)→O(1))
- HashMap：空间换维度（O(n²)→O(n))
- 差分：延迟计算（O(n)→O(1))