Hard

题目描述

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元格 matrix[x][y] 的集合。

如果两个子矩阵 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 中至少有一个坐标不同，那么这两个子矩阵也不相同：例如，如果 x1 != x1'。

示例 1：

输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。

示例 2：

输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。

示例 3：

输入：matrix = [[904]], target = 0
输出：0

提示：

  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i][j] <= 1000
  • -10^8 <= target <= 10^8

解题思路

这是一道经典的二维矩阵前缀和问题，可以通过降维的思想将其转化为一维数组的子数组和问题。

解题思路：

  1. 核心思想：枚举所有可能的上下边界，将二维问题转化为一维问题。对于固定的上下边界，问题转化为求一维数组中和为 target 的子数组个数。

  2. 具体步骤：

    • 枚举上边界 top（从 0 到 m-1）
    • 枚举下边界 bottom（从 top 到 m-1）
    • 对于固定的 [top, bottom] 区间，计算每列的和，形成一个一维数组
    • 在这个一维数组中，使用哈希表快速找出和为 target 的子数组个数

  3. 一维数组求解：使用前缀和 + 哈希表的经典方法。维护一个前缀和 prefixSum，对于当前位置，查找是否存在 prefixSum - target 的前缀和。

  4. 时间复杂度优化：通过逐行累加的方式，避免重复计算列和，使得总时间复杂度为 O(m² × n)，其中 m 为行数，n 为列数。

这种方法将二维问题巧妙地转化为多个一维问题，是处理矩阵区域和问题的经典技巧。

代码实现

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int result = 0;
        
        for (int top = 0; top < m; top++) {
            vector<int> colSum(n, 0);
            for (int bottom = top; bottom < m; bottom++) {
                // 累加当前行到列和中
                for (int j = 0; j < n; j++) {
                    colSum[j] += matrix[bottom][j];
                }
                
                // 在一维数组colSum中找和为target的子数组
                result += subarraySum(colSum, target);
            }
        }
        
        return result;
    }
    
private:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> prefixSumCount;
        prefixSumCount[0] = 1;
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num;
            count += prefixSumCount[prefixSum - k];
            prefixSumCount[prefixSum]++;
        }
        
        return count;
    }
};

class Solution:
    def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
        m, n = len(matrix), len(matrix[0])
        result = 0
        
        for top in range(m):
            col_sum = [0] * n
            for bottom in range(top, m):
                # 累加当前行到列和中
                for j in range(n):
                    col_sum[j] += matrix[bottom][j]
                
                # 在一维数组col_sum中找和为target的子数组
                result += self.subarray_sum(col_sum, target)
        
        return result
    
    def subarray_sum(self, nums: List[int], k: int) -> int:
        prefix_sum_count = {0: 1}
        prefix_sum = 0
        count = 0
        
        for num in nums:
            prefix_sum += num
            count += prefix_sum_count.get(prefix_sum - k, 0)
            prefix_sum_count[prefix_sum] = prefix_sum_count.get(prefix_sum, 0) + 1
        
        return count

public class Solution {
    public int NumSubmatrixSumTarget(int[][] matrix, int target) {
        int m = matrix.Length, n = matrix[0].Length;
        int result = 0;
        
        for (int top = 0; top < m; top++) {
            int[] colSum = new int[n];
            for (int bottom = top; bottom < m; bottom++) {
                // 累加当前行到列和中
                for (int j = 0; j < n; j++) {
                    colSum[j] += matrix[bottom][j];
                }
                
                // 在一维数组colSum中找和为target的子数组
                result += SubarraySum(colSum, target);
            }
        }
        
        return result;
    }
    
    private int SubarraySum(int[] nums, int k) {
        Dictionary<int, int> prefixSumCount = new Dictionary<int, int>();
        prefixSumCount[0] = 1;
        int prefixSum = 0;
        int count = 0;
        
        foreach (int num in nums) {
            prefixSum += num;
            if (prefixSumCount.ContainsKey(prefixSum - k)) {
                count += prefixSumCount[prefixSum - k];
            }
            if (prefixSumCount.ContainsKey(prefixSum)) {
                prefixSumCount[prefixSum]++;
            } else {
                prefixSumCount[prefixSum] = 1;
            }
        }
        
        return count;
    }
}

var numSubmatrixSumTarget = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let result = 0;
    
    for (let top = 0; top < m; top++) {
        const colSum = new Array(n).fill(0);
        for (let bottom = top; bottom < m; bottom++) {
            // 累加当前行到列和中
            for (let j = 0; j < n; j++) {
                colSum[j] += matrix[bottom][j];
            }
            
            // 在一维数组colSum中找和为target的子数组
            result += subarraySum(colSum, target);
        }
    }
    
    return result;
    
    function subarraySum(nums, k) {
        const prefixSumCount = new Map();
        prefixSumCount.set(0, 1);
        let prefixSum = 0;
        let count = 0;
        
        for (const num of nums) {
            prefixSum += num;
            count += prefixSumCount.get(prefixSum - k) || 0;
            prefixSumCount.set(prefixSum, (prefixSumCount.get(prefixSum) || 0) + 1);
        }
        
        return count;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(m² × n)外层两重循环枚举上下边界O(m²)，内层计算列和和一维子数组和各需O(n)
空间复杂度O(n)需要额外的数组存储列和，以及哈希表存储前缀和

相关题目