1. 问题背景与核心思路这道LeetCode 1074题要求我们统计矩阵中所有元素和等于目标值的子矩阵数量。子矩阵是指由原矩阵中连续的行和列组成的矩形区域。这个问题看似简单但直接暴力枚举所有可能的子矩阵会导致O(n²m²)的时间复杂度对于较大的矩阵显然不够高效。我最初尝试暴力解法时在100×100的测试用例上就超时了。经过思考发现可以将二维问题转化为一维问题来处理。核心思路分为两个关键步骤二维转一维通过固定左右边界将每一行在这两列之间的元素和压缩成一个一维数组。例如对于一个3×3的矩阵固定左边界为第1列右边界为第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]。为了优化空间我们不需要显式地存储前缀和数组而是使用哈希表来记录前缀和出现的次数。具体步骤如下初始化哈希表记录前缀和0出现1次因为空数组的和为0遍历数组计算当前的前缀和检查哈希表中是否存在当前前缀和 - target更新哈希表中当前前缀和的出现次数这种方法可以将时间复杂度从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) { MapInteger, 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 主函数解析参数检查首先检查矩阵是否为空如果是则直接返回0。双重循环枚举边界外层循环枚举左边界内层循环枚举右边界。这样我们考虑了所有可能的列范围。行和累加对于每一对左右边界计算每一行在这个列范围内的和存储在rowSum数组中。子数组统计调用subarraySum方法统计rowSum中和为target的子数组数量。3.2 辅助函数解析subarraySum方法实现了经典的前缀和哈希表技巧初始化哈希表记录前缀和0出现1次这对应空数组的情况。遍历数组计算当前的前缀和preSum。检查目标值如果preSum - k存在于哈希表中说明存在子数组的和为k。更新哈希表记录当前前缀和出现的次数。4. 时间复杂度分析让我们分析这个算法的时间复杂度外层循环枚举左边界O(n)次中层循环枚举右边界O(n)次从left到n-1内层循环计算行和O(m)次子数组统计对每个rowSum数组O(m)时间处理因此总时间复杂度为O(n²m)。空间复杂度主要是哈希表使用的O(m)空间。5. 实际应用中的优化技巧在实际编码面试或竞赛中有几点可以注意边界条件处理空矩阵、单行或单列矩阵等特殊情况要单独考虑。空间优化rowSum数组可以复用减少内存分配开销。提前终止如果矩阵元素都是正数且target为负数可以直接返回0。输入验证检查矩阵是否为矩形所有行长度相同。6. 常见错误与调试技巧在实现这个算法时容易犯以下几个错误哈希表初始化忘记初始化map.put(0,1)会导致漏计从数组开头开始的子数组。行和累加在右边界移动时应该在原有rowSum基础上累加而不是重新计算。索引越界确保矩阵访问不越界特别是当矩阵不是正方形时。整数溢出如果矩阵元素很大前缀和可能会溢出需要使用long类型。调试时可以先用小矩阵手动计算预期结果再与程序输出对比。例如matrix [[1,-1],[-1,1]], target 0这个案例有5个和为0的子矩阵可以用来验证代码正确性。7. 算法扩展与变种这个问题的解法可以扩展到一些变种问题最大子矩阵和将target改为求最大值可以用类似思路解决。矩形区域统计统计满足某些条件的矩形区域数量。三维情况如果是三维矩阵可以考虑类似的降维方法。此外这个前缀和哈希表的技巧在很多其他问题中也非常有用比如寻找和为特定值的子数组寻找最长的和为特定值的子数组统计满足某些条件的子数组数量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 countPython实现利用了defaultdict简化哈希表操作整体逻辑与Java版本一致。性能上Python可能稍慢于Java但代码更简洁。9. 实际应用场景这种子矩阵求和问题在实际中有多种应用图像处理统计图像特定区域的特征值数据分析统计满足条件的子数据集金融分析寻找特定模式的交易记录游戏开发地图或网格系统中的区域统计理解这类问题的解法可以帮助我们在面对类似的实际问题时快速找到解决方案。10. 个人实现心得在实际实现这个算法时我有几点深刻体会降维思想将二维问题转化为一维问题是关键突破点。这种降维思想在很多算法问题中都很有用。前缀和技巧前缀和配合哈希表是一种非常强大的工具可以高效解决许多求和问题。掌握这个技巧可以大大提高解题效率。边界条件算法看似简单但边界条件很容易出错。特别是哈希表初始化和行和累加部分需要特别注意。测试用例设计全面的测试用例很重要包括空矩阵、单元素矩阵、全正数/负数矩阵等特殊情况。性能优化在竞赛或面试中注意代码的常数优化比如减少不必要的对象创建和函数调用。这个问题的解法展示了如何将复杂问题分解为已知的简单问题是算法设计中分而治之思想的典型应用。掌握这种思维方式可以让我们在面对新问题时更有信心和方向。 
长河君 · 2026/11/3 16:14:09 · 阅读 1.2k LeetCode 1074：子矩阵和等于目标值的优化解法
1. 问题背景与核心思路这道LeetCode 1074题要求我们统计矩阵中所有元素和等于目标值的子矩阵数量。子矩阵是指由原矩阵中连续的行和列组成的矩形区域。这个问题看似简单但直接暴力枚举所有可能的子矩阵会导致O(n²m²)的时间复杂度对于较大的矩阵显然不够高效。我最初尝试暴力解法时在100×100的测试用例上就超时了。经过思考发现可以将二维问题转化为一维问题来处理。核心思路分为两个关键步骤二维转一维通过固定左右边界将每一行在这两列之间的元素和压缩成一个一维数组。例如对于一个3×3的矩阵固定左边界为第1列右边界为第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]。为了优化空间我们不需要显式地存储前缀和数组而是使用哈希表来记录前缀和出现的次数。具体步骤如下初始化哈希表记录前缀和0出现1次因为空数组的和为0遍历数组计算当前的前缀和检查哈希表中是否存在当前前缀和 - target更新哈希表中当前前缀和的出现次数这种方法可以将时间复杂度从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) { MapInteger, 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 主函数解析参数检查首先检查矩阵是否为空如果是则直接返回0。双重循环枚举边界外层循环枚举左边界内层循环枚举右边界。这样我们考虑了所有可能的列范围。行和累加对于每一对左右边界计算每一行在这个列范围内的和存储在rowSum数组中。子数组统计调用subarraySum方法统计rowSum中和为target的子数组数量。3.2 辅助函数解析subarraySum方法实现了经典的前缀和哈希表技巧初始化哈希表记录前缀和0出现1次这对应空数组的情况。遍历数组计算当前的前缀和preSum。检查目标值如果preSum - k存在于哈希表中说明存在子数组的和为k。更新哈希表记录当前前缀和出现的次数。4. 时间复杂度分析让我们分析这个算法的时间复杂度外层循环枚举左边界O(n)次中层循环枚举右边界O(n)次从left到n-1内层循环计算行和O(m)次子数组统计对每个rowSum数组O(m)时间处理因此总时间复杂度为O(n²m)。空间复杂度主要是哈希表使用的O(m)空间。5. 实际应用中的优化技巧在实际编码面试或竞赛中有几点可以注意边界条件处理空矩阵、单行或单列矩阵等特殊情况要单独考虑。空间优化rowSum数组可以复用减少内存分配开销。提前终止如果矩阵元素都是正数且target为负数可以直接返回0。输入验证检查矩阵是否为矩形所有行长度相同。6. 常见错误与调试技巧在实现这个算法时容易犯以下几个错误哈希表初始化忘记初始化map.put(0,1)会导致漏计从数组开头开始的子数组。行和累加在右边界移动时应该在原有rowSum基础上累加而不是重新计算。索引越界确保矩阵访问不越界特别是当矩阵不是正方形时。整数溢出如果矩阵元素很大前缀和可能会溢出需要使用long类型。调试时可以先用小矩阵手动计算预期结果再与程序输出对比。例如matrix [[1,-1],[-1,1]], target 0这个案例有5个和为0的子矩阵可以用来验证代码正确性。7. 算法扩展与变种这个问题的解法可以扩展到一些变种问题最大子矩阵和将target改为求最大值可以用类似思路解决。矩形区域统计统计满足某些条件的矩形区域数量。三维情况如果是三维矩阵可以考虑类似的降维方法。此外这个前缀和哈希表的技巧在很多其他问题中也非常有用比如寻找和为特定值的子数组寻找最长的和为特定值的子数组统计满足某些条件的子数组数量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 countPython实现利用了defaultdict简化哈希表操作整体逻辑与Java版本一致。性能上Python可能稍慢于Java但代码更简洁。9. 实际应用场景这种子矩阵求和问题在实际中有多种应用图像处理统计图像特定区域的特征值数据分析统计满足条件的子数据集金融分析寻找特定模式的交易记录游戏开发地图或网格系统中的区域统计理解这类问题的解法可以帮助我们在面对类似的实际问题时快速找到解决方案。10. 个人实现心得在实际实现这个算法时我有几点深刻体会降维思想将二维问题转化为一维问题是关键突破点。这种降维思想在很多算法问题中都很有用。前缀和技巧前缀和配合哈希表是一种非常强大的工具可以高效解决许多求和问题。掌握这个技巧可以大大提高解题效率。边界条件算法看似简单但边界条件很容易出错。特别是哈希表初始化和行和累加部分需要特别注意。测试用例设计全面的测试用例很重要包括空矩阵、单元素矩阵、全正数/负数矩阵等特殊情况。性能优化在竞赛或面试中注意代码的常数优化比如减少不必要的对象创建和函数调用。这个问题的解法展示了如何将复杂问题分解为已知的简单问题是算法设计中分而治之思想的典型应用。掌握这种思维方式可以让我们在面对新问题时更有信心和方向。