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

Categories:

题目描述
思路分析
1. 解法一：行压缩 + 前缀和计数（推荐）
相似题目

题目描述

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

思路分析

解法一：行压缩 + 前缀和计数（推荐）

核心思路：

固定上下边界行，将矩阵压缩为一维数组（列和）。

问题转化为一维数组中和为目标值的子数组数量。

使用前缀和 + 哈希表统计。

复杂度分析：

时间复杂度：O(m^2 n)，其中 m、n 为矩阵行列数。

空间复杂度：O(n)，存储列压缩数组与哈希表。

import java.util.*;

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
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和
304. 二维区域和检索 - 矩阵不可变	中等	前缀和
1074. 元素和为目标值的子矩阵数量	困难	前缀和
363. 矩形区域不超过 K 的最大数值和	困难	前缀和
525. 连续数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/63956518