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

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

题目描述

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

image-20260928214556766

image-20260928214556767

题意分析

统计元素和等于 target 的非空连续子矩阵。每个子矩阵由上下左右四条边界唯一确定，即使元素和相同，只要边界不同就分别计数。矩阵允许负数，扩张区间不一定让和增大，因此不能用普通滑动窗口按大小移动边界。

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

核心思路

[!blue]

先固定上边界 top 和下边界 bottom，令 colSum[c] 为这几行第 c 列的元素总和。此时原矩阵中左右边界为 left..right 的子矩阵，其元素和就是 colSum[left..right] 的区间和。上下边界固定后，连续列区间与子矩阵一一对应，所以问题变成统计一维数组中和为目标值的子数组。

令 P[r] 表示列 0..r 的前缀和，并把第 0 列之前的空前缀记为 0。区间 left..right 满足目标，当且仅当 P[left - 1] = P[right] - target。扫描到右端点时，用哈希表 cnt 保存此前各前缀和的出现次数，cnt[sum - target] 就是以当前列结尾的合法区间数量。

同一个前缀和可能来自多个位置，每个位置都代表不同的左边界，所以要累计频次。先查询历史前缀，再登记当前前缀，保证左边界不会落到右边界之后；预先登记一次空前缀 0，才能包含从第 0 列开始的区间。

对同一个 top，下边界每推进一行，只需把新行加到 colSum。每对上下边界各统计一次，内部又按唯一的右端点计数，因此所有目标子矩阵恰好被统计一次。

解题步骤

  • 枚举上边界 top，新建全零的 colSum。
  • 从 bottom = top 开始下移，每次执行 colSum[c] += matrix[bottom][c]，得到当前行区间的列和。
  • 为当前上下边界新建频次表，令 cnt[0] = 1，前缀和 sum = 0。
  • 依次扫描列和，先更新 sum，把 cnt[sum - target] 加入答案，再把 cnt[sum] 增加 1。
  • 处理完所有上下边界后返回总数。单行、单列以及 target = 0 都沿用相同流程。

代码实现

// 问题转化为一维数组中和为目标值的子数组数量。
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
}

复杂度分析

设矩阵有 m 行、n 列。

  • 时间复杂度：期望 $O(m^2n)$。共有 $m(m+1)/2$ 对上下边界，每对更新列和并扫描一次，哈希查询的期望时间为 $O(1)$。
  • 空间复杂度：$O(n)$。列和数组有 n 个元素，频次表至多保存 n + 1 个不同前缀和。

关键点总结

[!green]

  • 固定上下边界后，二维子矩阵和与一维列和区间完全相同。
  • 下边界推进时复用列和，但每对上下边界的前缀频次表必须独立。
  • 计数的对象是不同前缀位置，重复的前缀值也会产生不同区间。
  • 前缀差只依赖加减关系，不要求元素非负。

易错点总结

[!yellow]

  • bottom 必须从 top 开始，保证上下边界合法，也包含只有一行的子矩阵。
  • 下移 bottom 时要累加新行；更换 top 时则要清零，不能混用这两种更新。
  • 频次表漏掉 cnt[0] = 1，就会漏算从第 0 列开始的区间。
  • 当前前缀先入表，目标为零时会让它与自身配对，错误计入空区间。
  • 只保存前缀和是否出现过，或沿用上一对行边界的频次表，都会使计数失真。

相似题目

题目 难度 关联与区别
560. 和为 K 的子数组 中等 固定上下行并压成一维列和后，直接复用目标和子数组计数。
363. 矩形区域不超过 K 的最大数值和 困难 二维压缩相同，原题求不超过k的最大和，本题统计和恰好等于目标的全部矩形。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63956518
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！