和为目标值的子矩阵数量，如何把二维问题压缩成一维前缀和？

简化版

统计和为目标值的子矩阵，可以枚举上下边界，把二维矩阵压缩成一维数组。

固定 top 和 bottom 后，每一列在这两行之间的和形成一个数组。

问题就变成：这个一维数组中和为 target 的子数组有多少个，用前缀和哈希统计即可。

详细版

直接枚举所有子矩阵是 O(m^2 n^2)，再求和会更慢。

优化思路是固定两条横边。对每个列 c，计算从 top 到 bottom 的列和 colSum[c]。任意连续列区间的和，就对应一个子矩阵的和。

于是对 colSum 运行“和为 K 的子数组个数”：

prefix += x
ans += count.get(prefix - target) || 0
count[prefix]++

如果行数为 m、列数为 n，复杂度约为 O(m^2 n)。如果列数更少，也可以枚举左右边界压缩行。

完整版教学

一、为什么要降维

子矩阵有上下左右 4 个边界，直接枚举很容易到 O(m^2 n^2)。更麻烦的是，每个子矩阵还要快速求和。降维的核心是先固定两个维度的边界，把剩下的连续边界问题变成一维子数组问题。这样可以复用成熟的“前缀和 + 哈希统计目标和”模板。

记忆钩子：二维目标和子矩阵，固定两条边，剩下一维用和为 K。

思路	固定内容	剩余问题	复杂度倾向
暴力枚举四边	上下左右都枚举	逐个子矩阵判断	偏高
固定上下边	`top/bottom`	一维列和子数组	`O(m^2 n)`
固定左右边	`left/right`	一维行和子数组	`O(n^2 m)`

二、固定上下边界后发生了什么

假设固定 top = 1、bottom = 3。对每一列，把第 1 到第 3 行的元素加起来，得到 colSum。此时选择连续列 [l, r]，就对应原矩阵中行 [top,bottom]、列 [l,r] 的子矩阵。

原矩阵一块区域
top..bottom 行被压成一行 colSum
连续列区间 = 一个子矩阵

这个映射是一一对应的，不会漏也不会重。

三、一维目标和如何统计

对 colSum，统计和为 target 的连续子数组个数。使用前缀和哈希：

prefix[j] - prefix[i] = target
prefix[i] = prefix[j] - target

遍历到当前列时，查之前有多少个 prefix - target，这些都能和当前位置组成目标和子数组。

四、代码模板

实现如下：

function numSubmatrixSumTarget(matrix, target) {
  const m = matrix.length
  const n = matrix[0].length
  let ans = 0
  for (let top = 0; top < m; top++) {
    const colSum = new Array(n).fill(0)
    for (let bottom = top; bottom < m; bottom++) {
      for (let c = 0; c < n; c++) {
        colSum[c] += matrix[bottom][c]
      }
      ans += countSubarraySum(colSum, target)
    }
  }
  return ans
}

function countSubarraySum(arr, target) {
  const count = new Map([[0, 1]])
  let prefix = 0
  let ans = 0
  for (const x of arr) {
    prefix += x
    ans += count.get(prefix - target) || 0
    count.set(prefix, (count.get(prefix) || 0) + 1)
  }
  return ans
}

colSum 在 bottom 下移时增量更新，不需要每次从头计算列和。

五、带数字推演

矩阵：

1  -1
-1  1

目标 0。固定 top=0,bottom=0，colSum=[1,-1]，有 1 个和为 0 的子数组。固定 top=1,bottom=1，colSum=[-1,1]，也有 1 个。固定 top=0,bottom=1，colSum=[0,0]，和为 0 的子数组有 3 个。总共 5 个。

这个例子能看出压缩后的一维计数正好对应子矩阵计数。

六、常见误区与追问

误区：枚举子矩阵后再逐格求和。 会重复计算大量区域，复杂度太高。
误区：压缩后用滑动窗口。 矩阵元素可能有负数，一维数组也可能有负数，滑动窗口不稳。
误区：每次 bottom 改变都重新计算 colSum。 应该增量加当前行，节省一层成本。
追问：行列差异很大怎么优化？ 枚举较小维度的两条边，让平方项落在较小维度上。
追问：为什么哈希表存次数？ 因为要统计数量，同一个前缀和多次出现都能贡献不同子数组。

这些追问考的是二维到一维的建模能力。

七、加强记忆

目标和子矩阵记成“固定上下，列和压缩，套一维和为 K”。上下边界确定后，连续列区间就是一个子矩阵；列和数组里的子数组和，就是这个子矩阵的和。用前缀和哈希统计数量，哈希表存次数。若矩阵很扁，就选择枚举更短的维度做平方项。

简化版

详细版