线性动态规划：统计子矩阵中目标和（子矩阵和等于目标值的子矩阵个数）

题目描述

给定一个 m x n 的整数矩阵 matrix 和一个整数 target，要求统计出矩阵中和等于 target 的子矩阵的个数。
注意：

• 子矩阵是原矩阵中连续的行和连续的列构成的矩形区域。
• 子矩阵至少包含 1×1 的元素。
• 统计的是不同位置的子矩阵，即使两个子矩阵元素和相同但位置不同，也算作不同的子矩阵。

解题思路

1. 核心转换

如果暴力枚举所有子矩阵，时间复杂度是 \(O(m^2 n^2)\)，在 m 和 n 达到 100 左右时就会超时。
为了高效计算，我们可以利用“行前缀和”+“列压缩”+“哈希表”的技巧：

1. 先计算每行的前缀和，便于快速求一行中某一段的和。
2. 枚举上下边界（两行 r1 和 r2 之间的区域）。
3. 将 r1 到 r2 之间的每一列压缩成一个数字，即这个矩形区域中每一列的和，形成一个长度为 n 的数组。
4. 问题转化为：在一个一维数组中，求有多少个子数组的和等于 target。
   这是一个经典的一维前缀和+哈希表问题（类似于“和为K的子数组个数”）。

逐步讲解

步骤1：行的前缀和

为了方便求原矩阵中第 i 行从列 j1 到 j2 的和，我们预先计算行前缀和：

rowPrefix[i][j] = matrix[i][0] + matrix[i][1] + ... + matrix[i][j-1]（通常前缀和下标从1开始，方便计算）

但为了直观，可以定义 rowSum[i][j] = matrix[i][0] + ... + matrix[i][j]，这样从列 c1 到 c2 的和就是
rowSum[i][c2] - (c1>0 ? rowSum[i][c1-1] : 0)。
不过实现时，我们可以直接在枚举列的过程中累加，避免存储行前缀和数组，但这里我们先按存储行前缀和的方法思考。

优化：其实可以不必单独建行前缀和数组，枚举上下边界时，直接逐列累加即可。

步骤2：枚举上边界和下边界

外层循环：上边界 top 从 0 到 m-1。
内层循环：下边界 bottom 从 top 到 m-1。

步骤3：将多行压缩成一维数组

在确定了 top 和 bottom 后，我们计算一个数组 colSum[0..n-1]：

colSum[j] = 矩阵中第 j 列从行 top 到 bottom 的所有元素之和

这个计算可以用逐行累加来避免每次重新计算：

• 当 bottom 向下扩展一行时，colSum[j] += matrix[bottom][j]。

步骤4：在一维数组中求和为 target 的子数组个数

已知数组 colSum 长度为 n，求其有多少个子数组的和等于 target。

用一维前缀和+哈希表方法：

• 设 prefixSum 为从 colSum[0] 累加到当前元素的前缀和。
• 要找一个子数组 [l, r] 和等于 target，即
  prefixSum[r] - prefixSum[l-1] = target。
  移项得 prefixSum[r] - target = prefixSum[l-1]。

所以我们遍历 colSum 数组：

1. 用哈希表 map 记录之前出现过的前缀和值的次数。
2. 当前的前缀和是 currentPrefix，如果 currentPrefix - target 在哈希表中存在，说明存在一些左边界 l 满足条件，累加其个数到答案。
3. 将当前前缀和加入哈希表。

注意：初始化哈希表时，map[0] = 1，表示前缀和为 0 出现一次（相当于左边界是 0 的前一个位置）。

步骤5：整体流程

1. 初始化 ans = 0。
2. 遍历上边界 top = 0..m-1：
   • 初始化长度 n 的数组 colSum 全为 0。
   • 遍历下边界 bottom = top..m-1：
     • 遍历列 j = 0..n-1：
       • colSum[j] += matrix[bottom][j]。
     • 现在有了一个一维数组 colSum，用上述哈希表方法计算它的和为 target 的子数组个数，加到 ans 中。
3. 返回 ans。

例子说明

例如：

matrix = [
  [1, 0, 1],
  [0, 1, 0],
  [1, 0, 1]
]
target = 2

我们手动推导一部分：

top=0, bottom=0：
colSum = [1, 0, 1]
一维数组中等于 2 的子数组：索引 [0,2] 和为 1+0+1=2，所以个数加 1。
但一维前缀和方法会找到：前缀和变化：0→1→1→2，其中 2-2=0 在哈希表中，说明有 1 个。确实。

top=0, bottom=1：
colSum = [1,1,1]
子数组和为 2 的：[0,1] 和 [1,2]，共 2 个。

这样继续枚举所有上下边界，最后得到总个数。

复杂度分析

• 枚举上下边界：O(m²)
• 在上下边界确定后，压缩为 colSum 需要 O(n)，然后在 colSum 上计算一维子数组个数需要 O(n)
• 总复杂度 O(m² n)
  如果 m>n 可以转置矩阵，保证较小的维度平方，得到 O(min(m,n)² * max(m,n))。

空间复杂度 O(n) 用于存储 colSum 和哈希表。

代码思路（伪代码）

def numSubmatrixSumTarget(matrix, target):
    m, n = len(matrix), len(matrix[0])
    ans = 0
    for top in range(m):
        colSum = [0] * n
        for bottom in range(top, m):
            for j in range(n):
                colSum[j] += matrix[bottom][j]
            # 在 colSum 上计算和为 target 的子数组个数
            prefixSumCount = {0: 1}
            current = 0
            for val in colSum:
                current += val
                if (current - target) in prefixSumCount:
                    ans += prefixSumCount[current - target]
                prefixSumCount[current] = prefixSumCount.get(current, 0) + 1
    return ans

总结

这道题的关键是将二维子矩阵和问题转化为一维子数组和问题，通过枚举上下边界并压缩列，再用哈希表高效统计一维子数组和等于目标值的个数。这是二维区域和统计的经典技巧，在类似“子矩阵和等于K”的问题中很常用。