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

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

问题定义与核心挑战

给定二维矩阵 matrix 和目标值 target，需统计 所有和为 target 的非空子矩阵数量。直接枚举所有子矩阵的时间复杂度为 O(m²n²)（m、n 为矩阵行列数），无法通过大数据用例，因此需要降维优化。

核心思路：二维转一维 + 前缀和哈希表

将二维问题转化为多个一维子问题：

1. 固定上下边界：遍历所有可能的上边界 top 和下边界 bottom，将两边界之间的列和压缩为一维数组 colSum（colSum[col] 表示 top 到 bottom 行、第 col 列的和）。
2. 一维子数组统计：对 colSum 数组，使用前缀和 + 哈希表的方法，统计和为 target 的子数组数量（时间复杂度 O(n)）。

算法步骤详解

步骤 1：遍历上下边界

• 枚举所有可能的上边界 top（从第 0 行到第 m-1 行）。
• 对每个 top，初始化 colSum 数组（记录列和），并枚举下边界 bottom（从 top 到第 m-1 行）。

步骤 2：更新列和数组 colSum

对于当前 bottom，将 matrix[bottom][col] 累加到 colSum[col] 中，得到 top 到 bottom 行的列和。

步骤 3：统计一维子数组和为 target 的数量

对 colSum 数组，使用前缀和 + 哈希表：

• 前缀和 currentSum：记录当前遍历到第 col 列时的前缀和（前 col+1 列的和）。
• 哈希表 prefixCounts：记录前缀和出现的次数（初始时 prefixCounts.put(0, 1)，表示前缀和为 0 的情况，对应子数组从第 0 列开始）。
• 对于每个列和 num：
  • 计算 need = currentSum - target，若 need 存在于 prefixCounts，则累加对应次数（即存在以当前列为结尾的子数组和为 target）。
  • 更新 currentSum 并记录到 prefixCounts 中。

完整代码（Java）

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 ans = 0;

        // 枚举上边界 top
        for (int top = 0; top < m; top++) {
            int[] colSum = new int[n]; // 记录当前上下边界之间的列和
            // 枚举下边界 bottom（从 top 开始，逐步扩展）
            for (int bottom = top; bottom < m; bottom++) {
                // 更新列和：加上当前行 bottom 的元素
                for (int col = 0; col < n; col++) {
                    colSum[col] += matrix[bottom][col];
                }
                // 统计当前 colSum 中，和为 target 的子数组数量
                ans += countSubarrays(colSum, target);
            }
        }

        return ans;
    }

    /**
     * 统计一维数组 nums 中，和为 target 的子数组数量
     * 使用前缀和 + 哈希表优化，时间复杂度 O(n)
     */
    private int countSubarrays(int[] nums, int target) {
        int count = 0;
        int currentSum = 0;
        Map<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1); // 初始状态：前缀和为 0 出现 1 次（对应空数组）

        for (int num : nums) {
            currentSum += num;
            // 寻找是否存在前缀和为 currentSum - target 的情况
            int need = currentSum - target;
            if (prefixCounts.containsKey(need)) {
                count += prefixCounts.get(need);
            }
            // 更新当前前缀和的出现次数
            prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);
        }

        return count;
    }
}

复杂度分析

• 时间复杂度：O(m²n)。

  • 外层遍历上下边界：O(m²)（m 行，每行最多遍历 m 次）。
  • 内层处理列和与一维子数组：O(n)（每轮列和更新 O(n)，一维统计 O(n)）。
    总复杂度为 O(m² × n)，对于 m=100、n=100，计算量为 100²×100=1e6，高效可行。

• 空间复杂度：O(n)。

  • colSum 数组和哈希表最多占用 O(n) 空间（n 为列数）。

示例验证

示例 1（输入 matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0）：

• 当 top=0、bottom=0 时，colSum = [0,1,0]，统计得 2 个 子数组（[0]、[0]）。
• 当 top=2、bottom=2 时，colSum = [0,1,0]，同样统计得 2 个 子数组。
• 总数量为 2+2=4，符合示例输出。

示例 2（输入 matrix = [[1,-1],[-1,1]], target = 0）：

• 当 top=0、bottom=1 时，colSum = [0,0]，统计得 3 个 子数组（[0]、[0,0]、[0]）。
• 结合其他边界组合，最终总数量为 5，符合示例输出。

该方法通过二维转一维和前缀和哈希表，高效将复杂度从 O(m²n²) 降至 O(m²n)，是处理二维子矩阵和问题的经典优化思路。