LeetCode 1074：子矩阵和等于目标值的优化解法

发布时间：2026/11/3 16:14:14
LeetCode 1074：子矩阵和等于目标值的优化解法

1. 问题背景与核心思路

这道LeetCode 1074题要求我们统计矩阵中所有元素和等于目标值的子矩阵数量。子矩阵是指由原矩阵中连续的行和列组成的矩形区域。这个问题看似简单，但直接暴力枚举所有可能的子矩阵会导致O(n²m²)的时间复杂度，对于较大的矩阵显然不够高效。

我最初尝试暴力解法时，在100×100的测试用例上就超时了。经过思考，发现可以将二维问题转化为一维问题来处理。核心思路分为两个关键步骤：

  1. 二维转一维：通过固定左右边界，将每一行在这两列之间的元素和压缩成一个一维数组。例如对于一个3×3的矩阵，固定左边界为第1列，右边界为第2列，那么每一行在这两列之间的和就构成一个新的一维数组。

  2. 前缀和+哈希表：对这个一维数组，使用前缀和配合哈希表来快速统计和为target的子数组数量。这个技巧来自经典的LeetCode 560题（和为K的子数组）。

2. 算法详细解析

2.1 二维转一维的压缩过程

让我们用一个具体例子来说明这个转换过程。考虑以下3×3矩阵：

1 2 3 4 5 6 7 8 9

假设我们固定左边界为第0列，右边界为第1列。那么每一行在这两列之间的和为：

  • 第0行：1 + 2 = 3
  • 第1行：4 + 5 = 9
  • 第2行：7 + 8 = 15

这样就得到了压缩后的一维数组[3, 9, 15]。接下来，我们需要在这个一维数组中找到所有和为target的子数组。

2.2 前缀和与哈希表的应用

前缀和是一种常用的技巧，可以快速计算任意子数组的和。定义前缀和数组prefix，其中prefix[i]表示数组前i个元素的和。那么子数组[i,j]的和就可以表示为prefix[j] - prefix[i-1]。

为了优化空间，我们不需要显式地存储前缀和数组，而是使用哈希表来记录前缀和出现的次数。具体步骤如下：

  1. 初始化哈希表，记录前缀和0出现1次（因为空数组的和为0）
  2. 遍历数组，计算当前的前缀和
  3. 检查哈希表中是否存在（当前前缀和 - target）
  4. 更新哈希表中当前前缀和的出现次数

这种方法可以将时间复杂度从O(n²)降低到O(n)。

3. Java代码实现与逐行解析

以下是完整的Java实现，我将逐行解释关键部分：

import java.util.HashMap; import java.util.Map; class Solution { public int numSubmatrixSumTarget(int[][] matrix, int target) { int m = matrix.length; if (m == 0) return 0; int n = matrix[0].length; int ans = 0; // 枚举左边界 for (int left = 0; left < n; left++) { int[] rowSum = new int[m]; // 枚举右边界 for (int right = left; right < n; right++) { // 把每一行 [left, right] 的和累加到 rowSum for (int i = 0; i < m; i++) { rowSum[i] += matrix[i][right]; } // 求 rowSum 中和为 target 的子数组数量 ans += subarraySum(rowSum, target); } } return ans; } // LeetCode 560: 和为 K 的子数组个数 private int subarraySum(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); int preSum = 0; int count = 0; for (int num : nums) { preSum += num; if (map.containsKey(preSum - k)) { count += map.get(preSum - k); } map.put(preSum, map.getOrDefault(preSum, 0) + 1); } return count; } }

3.1 主函数解析

  1. 参数检查：首先检查矩阵是否为空，如果是则直接返回0。
  2. 双重循环枚举边界：外层循环枚举左边界，内层循环枚举右边界。这样我们考虑了所有可能的列范围。
  3. 行和累加：对于每一对左右边界，计算每一行在这个列范围内的和，存储在rowSum数组中。
  4. 子数组统计：调用subarraySum方法统计rowSum中和为target的子数组数量。

3.2 辅助函数解析

subarraySum方法实现了经典的前缀和+哈希表技巧：

  1. 初始化哈希表：记录前缀和0出现1次，这对应空数组的情况。
  2. 遍历数组：计算当前的前缀和preSum。
  3. 检查目标值：如果preSum - k存在于哈希表中，说明存在子数组的和为k。
  4. 更新哈希表：记录当前前缀和出现的次数。

4. 时间复杂度分析

让我们分析这个算法的时间复杂度：

  1. 外层循环：枚举左边界，O(n)次
  2. 中层循环：枚举右边界，O(n)次（从left到n-1）
  3. 内层循环：计算行和，O(m)次
  4. 子数组统计：对每个rowSum数组，O(m)时间处理

因此总时间复杂度为O(n²m)。空间复杂度主要是哈希表使用的O(m)空间。

5. 实际应用中的优化技巧

在实际编码面试或竞赛中，有几点可以注意：

  1. 边界条件处理：空矩阵、单行或单列矩阵等特殊情况要单独考虑。
  2. 空间优化：rowSum数组可以复用，减少内存分配开销。
  3. 提前终止：如果矩阵元素都是正数且target为负数，可以直接返回0。
  4. 输入验证：检查矩阵是否为矩形（所有行长度相同）。

6. 常见错误与调试技巧

在实现这个算法时，容易犯以下几个错误：

  1. 哈希表初始化：忘记初始化map.put(0,1)会导致漏计从数组开头开始的子数组。
  2. 行和累加：在右边界移动时，应该在原有rowSum基础上累加，而不是重新计算。
  3. 索引越界：确保矩阵访问不越界，特别是当矩阵不是正方形时。
  4. 整数溢出：如果矩阵元素很大，前缀和可能会溢出，需要使用long类型。

调试时可以先用小矩阵手动计算预期结果，再与程序输出对比。例如：

matrix = [[1,-1],[-1,1]], target = 0

这个案例有5个和为0的子矩阵，可以用来验证代码正确性。

7. 算法扩展与变种

这个问题的解法可以扩展到一些变种问题：

  1. 最大子矩阵和：将target改为求最大值，可以用类似思路解决。
  2. 矩形区域统计：统计满足某些条件的矩形区域数量。
  3. 三维情况：如果是三维矩阵，可以考虑类似的降维方法。

此外，这个前缀和+哈希表的技巧在很多其他问题中也非常有用，比如：

  • 寻找和为特定值的子数组
  • 寻找最长的和为特定值的子数组
  • 统计满足某些条件的子数组数量

8. 不同语言实现对比

虽然我们主要讨论了Java实现，但其他语言的实现思路类似。以下是Python的实现对比：

from collections import defaultdict class Solution: def numSubmatrixSumTarget(self, matrix, target): m, n = len(matrix), len(matrix[0]) count = 0 for left in range(n): row_sum = [0] * m for right in range(left, n): for i in range(m): row_sum[i] += matrix[i][right] count += self.subarraySum(row_sum, target) return count def subarraySum(self, nums, k): prefix_counts = defaultdict(int) prefix_counts[0] = 1 current_sum = 0 count = 0 for num in nums: current_sum += num count += prefix_counts.get(current_sum - k, 0) prefix_counts[current_sum] += 1 return count

Python实现利用了defaultdict简化哈希表操作，整体逻辑与Java版本一致。性能上，Python可能稍慢于Java，但代码更简洁。

9. 实际应用场景

这种子矩阵求和问题在实际中有多种应用：

  1. 图像处理：统计图像特定区域的特征值
  2. 数据分析：统计满足条件的子数据集
  3. 金融分析：寻找特定模式的交易记录
  4. 游戏开发：地图或网格系统中的区域统计

理解这类问题的解法，可以帮助我们在面对类似的实际问题时快速找到解决方案。

10. 个人实现心得

在实际实现这个算法时，我有几点深刻体会：

  1. 降维思想：将二维问题转化为一维问题是关键突破点。这种降维思想在很多算法问题中都很有用。

  2. 前缀和技巧：前缀和配合哈希表是一种非常强大的工具，可以高效解决许多求和问题。掌握这个技巧可以大大提高解题效率。

  3. 边界条件：算法看似简单，但边界条件很容易出错。特别是哈希表初始化和行和累加部分需要特别注意。

  4. 测试用例：设计全面的测试用例很重要，包括空矩阵、单元素矩阵、全正数/负数矩阵等特殊情况。

  5. 性能优化：在竞赛或面试中，注意代码的常数优化，比如减少不必要的对象创建和函数调用。

这个问题的解法展示了如何将复杂问题分解为已知的简单问题，是算法设计中"分而治之"思想的典型应用。掌握这种思维方式，可以让我们在面对新问题时更有信心和方向。