LeetCode 1074. 元素和为目标值的子矩阵数量

约 11 分钟
文章信息 10 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 字节跳动 微软 美团 阿里巴巴 拼多多
标签
数组 哈希表 矩阵 前缀和
目录

题目描述

✅ 1074. 元素和为目标值的子矩阵数量

题意分析

给一个 m × n 的整数矩阵和一个目标值 target，统计有多少个非空子矩阵（由连续的若干行与连续的若干列围成的矩形区域）内元素之和恰好等于 target。两个子矩阵只要四个边界不完全相同就算不同。

先数一数规模：子矩阵由「上边界、下边界、左边界、右边界」四个量确定，共 $O(m^2 n^2)$ 个。约束是 1 ≤ m, n ≤ 100，也就是最多约 $2.5 \times 10^7$ 个子矩阵——枚举它们本身尚可接受，但如果每个还要 $O(mn)$ 地求和就彻底不行了。所以复杂度的关键在于「怎么快速拿到区域和」。

更重要的是元素可以为负（-1000 ≤ matrix[i][j] ≤ 1000）。有负数意味着区域和不随边界扩张而单调，滑动窗口、双指针这类依赖单调性的技巧全部失效，只能老老实实枚举加查表。

那么怎么把四重枚举压下来？注意到一维数组上有个成熟得多的对应问题——「和为 k 的子数组数量」，它只需要枚举右端点、用哈希表查前缀和，$O(n)$ 就能解决。二维要能借力，就得把其中两个维度先固定住，让剩下的部分退化成一维。固定上下两条水平边界之后，每一列在这段行区间内的和是确定的，整个矩形就压成了一个长度为 n 的数组，问题正好变成一维版本。

边界：target 可以是 0，且矩阵里可能有大量 0，此时答案会很大，但仍在 int 范围内（题目保证）；子矩阵必须非空，所以行区间与列区间都至少含一行 / 一列。

解法：行压缩 + 前缀和计数

核心思路

暴力做法是四重循环枚举四条边界、再用两重循环求和，$O(m^2 n^2 \cdot mn)$，完全不可行。加上二维前缀和把求和降到 $O(1)$ 之后是 $O(m^2 n^2)$，$100^4 = 10^8$ 在时限内很危险。瓶颈在于：左右两条列边界仍然是独立枚举的，而这正是一维「和为 k 的子数组」用哈希表消掉的那一维。

于是采用行压缩：外层枚举上边界 top（0 到 m-1），内层枚举下边界 bottom（top 到 m-1）。对固定的一对 (top, bottom)，定义

colSum[c] = matrix[top][c] + matrix[top+1][c] + ... + matrix[bottom][c]，

也就是第 c 列在这段行区间内的和。这样，「上下边界为 (top, bottom)、左右边界为 (l, r) 的子矩阵和」就等于「colSum 数组上区间 [l, r] 的和」。二维问题被完整地降成一维。

colSum 不需要每次重算：当 bottom 从 top 递增到 m-1 时，只要把第 bottom 行整行累加进 colSum 即可，单次 $O(n)$。

接下来在 colSum 上求「和为 target 的子数组个数」，用前缀和加哈希表：从左到右扫描，维护当前前缀和 sum，则以当前位置为右端点、和为 target 的子数组个数，等于哈希表中键 sum - target 的出现次数（因为 sum - 前缀和 = target ⟺ 前缀和 = sum - target）。查完再把当前 sum 记入表中。

不变量：扫描到 colSum 的下标 c 时，cnt 中记录的是前缀和 pre[0], pre[1], ..., pre[c] 的出现次数分布（其中 pre[0] = 0 表示空前缀），sum 等于 pre[c+1]。 于是 cnt[sum - target] 恰好是以 c 为右端点的合法子数组个数。

正确性可以分两层看：任意子矩阵都唯一对应一组 (top, bottom, left, right)；外层恰好枚举一次 (top, bottom)，而前缀和计数又恰好统计一次对应的 [left, right]。反过来，哈希表产生的每一对前缀位置都对应一个非空列区间，因此不会漏算，也不会把非法区域或同一子矩阵重复计入。

两个细节决定成败。一是 cnt 必须预置 {0: 1}，它代表「空前缀」，负责统计那些从下标 0 开始就满足条件的子数组；漏掉它会漏算一整类答案。二是先查询后写入，保证配对的左端点严格在当前位置之前，子数组非空。

每换一对 (top, bottom) 都要新建一张哈希表，因为不同行区间对应的是完全不同的一维数组，前缀和不能混用。

解题步骤

  • 外层固定 top，内层 bottom 从 top 开始递增：这样每对 (top, bottom) 都恰好被枚举一次，且 bottom ≥ top 保证行区间非空。
  • colSum 在每个新的 top 处清零，在 bottom 递增时增量累加：清零必须放在 top 的循环体内、bottom 的循环之外；增量累加让维护 colSum 的总代价保持在 $O(m^2 n)$ 而不是 $O(m^3 n)$。
  • 每对 (top, bottom) 新建哈希表并预置 {0: 1}：新建是因为一维数组换了；预置 0 是为了让「从最左端开始」的子数组也能被统计。
  • 扫描时先 res += cnt[sum - target]，再 cnt[sum]++：顺序颠倒会把「长度为 0 的空子数组」算进去（当 target == 0 时尤其明显）。
  • 哈希表的键是前缀和，值是出现次数：因为同一个前缀和可能出现多次，每次都能贡献一个合法子数组，必须计数而不是只记布尔或下标。
  • 累加结果用 int 即可：题目保证答案在 32 位范围内；但注意前缀和本身最大约 100 × 100 × 1000 = 10^7，也在 int 内。

以样例 matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]、target = 0 走一遍，正确答案是 4。

top = 0：colSum 清零为 [0, 0, 0]。
　bottom = 0：加入第 0 行，colSum = [0, 1, 0]。扫描：cnt = {0: 1}，sum = 0；
　　c = 0：sum = 0，查 cnt[0 - 0] = cnt[0] = 1，res = 1（对应子矩阵就是单个 matrix[0][0] = 0）；写入后 cnt = {0: 2}。
　　c = 1：sum = 1，查 cnt[1] = 0，res 不变；cnt = {0: 2, 1: 1}。
　　c = 2：sum = 1，查 cnt[1] = 1，res = 2（对应列区间 [2, 2]，即 matrix[0][2] = 0）；cnt = {0: 2, 1: 2}。
　bottom = 1：加入第 1 行，colSum = [1, 2, 1]。扫描：cnt = {0: 1}，sum 依次为 1、3、4，查 cnt[1]、cnt[3]、cnt[4] 均为 0，res 仍为 2。
　bottom = 2：加入第 2 行，colSum = [1, 3, 1]。扫描：sum 依次为 1、4、5，同样查不到，res 仍为 2。
top = 1：colSum 重新清零。
　bottom = 1：colSum = [1, 1, 1]，sum 依次为 1、2、3，查不到，res 仍为 2。
　bottom = 2：colSum = [1, 2, 1]，同上查不到。
top = 2：colSum 清零。
　bottom = 2：colSum = [0, 1, 0]，与 top = bottom = 0 时结构相同，贡献 2，res = 4。

最终返回 4，与预期一致。这四个子矩阵分别是四个角上的单元素 0：(0,0)、(0,2)、(2,0)、(2,2)。

若忘记预置 cnt = {0: 1}，上面 c = 0 处的查询 cnt[0] 会得到 0，res 少加 1；top = 2 那一轮同样少加 1，最终返回 2，正确答案是 4。若把 colSum 的清零误写到 top 循环之外（所有 top 共用一份），top = 1 时 colSum 会带着第 0 行的和进来，所有区域和整体偏大，答案完全错乱。

代码实现

import java.util.HashMap;
import java.util.Map;

// 问题转化为一维数组中和为目标值的子数组数量。
class Solution {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int res = 0;

        for (int top = 0; top < m; top++) {
            int[] colSum = new int[n];
            for (int bottom = top; bottom < m; bottom++) {
                for (int c = 0; c < n; c++) {
                    colSum[c] += matrix[bottom][c];
                }

                Map<Integer, Integer> cnt = new HashMap<>();
                cnt.put(0, 1);
                int sum = 0;
                for (int v : colSum) {
                    sum += v;
                    res += cnt.getOrDefault(sum - target, 0);
                    cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
                }
            }
        }

        return res;
    }
}

// 问题转化为一维数组中和为目标值的子数组数量。
func numSubmatrixSumTarget(matrix [][]int, target int) int {
	m, n := len(matrix), len(matrix[0])
	res := 0

	for top := 0; top < m; top++ {
		colSum := make([]int, n)
		for bottom := top; bottom < m; bottom++ {
			for c := 0; c < n; c++ {
				colSum[c] += matrix[bottom][c]
			}

			cnt := map[int]int{0: 1}
			sum := 0
			for _, v := range colSum {
				sum += v
				res += cnt[sum-target]
				cnt[sum]++
			}
		}
	}

	return res
}

复杂度分析

  • 时间复杂度：$O(m^2 n)$（哈希操作按均摊 $O(1)$ 计）。(top, bottom) 共 $O(m^2)$ 对，每对做两趟长度为 n 的遍历：一趟更新 colSum，一趟统计前缀和。若矩阵高度远大于宽度，可以对称地固定左右边界、压缩行，使复杂度变为 $O(\min(m,n)^2\max(m,n))$；本实现保留更直观的行压缩版本。
  • 空间复杂度：$O(n)$，凭的是 colSum 长度为 n，哈希表最多存 n + 1 个不同的前缀和，且每对 (top, bottom) 用完即弃，不会累积。

关键点总结

  • 二维区间问题的通用降维手法是「固定两条边界，把另外两维压成一维」。压缩之后要能一眼认出它变成了哪道一维经典题——本题压缩后就是 560「和为 K 的子数组」。这个套路同样适用于 85 最大矩形、363 矩形区域不超过 K 的最大数值和。
  • 有负数就不要想单调性。滑动窗口、双指针、前缀和二分全都建立在「和随区间扩张单调」上，元素可负时只能用「枚举右端点 + 哈希查左端点」这种不依赖单调性的方法。
  • 前缀和哈希表的两条铁律：预置 {0: 1} 代表空前缀；先查询后写入保证子数组非空且不重复。这两处几乎是所有前缀和计数题的固定失分点。
  • 增量维护 colSum（bottom 每前进一行就累加一行）把行压缩的代价从 $O(m^3 n)$ 降到 $O(m^2 n)$，是本题复杂度达标的关键；同理，哈希表必须每对边界重建，不能为了「省事」复用。
  • 完整的正确性来自一一对应：固定的行区间把矩形映射为 colSum 的连续子数组，而每个矩形的上下边界唯一、左右边界也只会被前缀和配对一次，因此既不漏也不重。
  • 面试视角：先说清「四重枚举 → 二维前缀和 → 行压缩 + 一维哈希」这条优化链路，再动手写代码。面试官常追问「如果 m 远大于 n 怎么办」——答「按较小的那一维做压缩，复杂度取 $O(\min(m, n)^2 \cdot \max(m, n))$」；另一个追问是「改成求和不超过 k 的最大子矩阵呢」——那就是 363 题，哈希表要换成有序集合配合二分。

易错点总结

  • 错误写法：哈希表不预置 {0: 1}：matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]、target = 0 → 所有从最左列开始的合法子矩阵都被漏掉，返回 2，正确答案是 4。
  • 错误写法：先 cnt[sum]++ 再 res += cnt[sum - target]：matrix = [[0]]、target = 0 → 当前前缀和把自己算成配对对象，返回 2，正确答案是 1。
  • 错误写法：colSum 只创建一次、放在 top 循环之外：matrix = [[1, 0], [0, 1]]、target = 1 → top = 1 时 colSum 仍带着第 0 行的和，所有区域和整体偏大，返回值与正确答案 6 完全不符。
  • 错误写法：哈希表在 top 循环外只建一次，(top, bottom) 之间复用：matrix = [[0, 1, 0], [1, 1, 1], [0, 1, 0]]、target = 0 → 不同行区间的前缀和被混在一起配对，凑出大量根本不存在的子矩阵，返回值远大于 4。
  • 错误写法：bottom 从 0 开始而不是从 top 开始：matrix = [[1]] → 会枚举出 bottom < top 的非法行区间，colSum 的含义失效，结果不可预测。
  • 错误写法：把 colSum 的累加写成 colSum[c] = matrix[bottom][c]（赋值而非累加）：matrix = [[1, 1], [1, 1]]、target = 2 → 每次只统计单独一行，跨行的子矩阵全部丢失，返回 3，正确答案是 4。
  • 错误写法：查询用 cnt[target - sum]：matrix = [[1, 2, 3]]、target = 3 → 最后一列查的是 3 - 6 = -3 而不是 6 - 3 = 3，漏掉子矩阵 [3]，返回 1，正确答案是 2。前缀和的配对方向是 pre_left = sum - target，不能写反。
  • 低效写法：用二维前缀和 + 四重循环枚举四条边界：m = n = 100 → 需要检查约 $10^8$ 个矩形，逻辑虽正确，却做了大量不必要的工作并可能逼近时限；行压缩把主循环量级降到约 $10^6$。
  • 错误写法：以为元素非负而使用滑动窗口找区间和：matrix = [[1, -1, 0]]、target = 0 → 区间和不单调，窗口收缩条件失效，会漏掉 [0, 1] 与 [2, 2] 等答案。题目明确允许负数。
  • 错误写法：哈希表的值只存布尔或最后一次出现的下标：matrix = [[0, 0]]、target = 0 → 前缀和 0 出现了三次（含空前缀），只记布尔会把三次配对压成一次，返回值小于正确答案 3。必须记出现次数。

相似题目

题目 难度 考察点
560. 和为 K 的子数组 中等 本题行压缩之后就退化成它，是必须先掌握的一维原型
LCR 010. 和为 K 的子数组 中等 与 560 同题，可用来检验「预置空前缀」与「先查后写」是否已成肌肉记忆
974. 和可被 K 整除的子数组 中等 哈希键换成前缀和的余数，还要处理负数取模的修正
525. 连续数组 中等 把 0 映射成 -1 后转成「和为 0 的最长子数组」，表里存最早下标而非计数
325. 和等于 k 的最长子数组长度 中等 求最长而非计数，因此哈希表只保留每个前缀和的最早出现位置
304. 二维区域和检索 - 矩阵不可变 中等 二维前缀和的模板题，是本题「$O(1)$ 求区域和」那条优化路线的基础
363. 矩形区域不超过 K 的最大数值和 困难 同样的行压缩骨架，但一维子问题变成「和不超过 K 的最大值」，哈希表要换成有序集合加二分
面试题 17.05. 字母与数字 中等 把字母与数字映射成 ±1 后求最长平衡子数组，是 525 的换皮版