1. 问题背景与理解今天遇到一道挺有意思的算法题 - LeetCode 1074题元素和为目标值的子矩阵数量。题目要求我们统计给定二维矩阵中所有元素和等于目标值的子矩阵的个数。这道题乍看简单但实际考察了多个算法知识点的综合运用。我刚看到题目时第一反应是暴力解法枚举所有可能的子矩阵计算它们的和然后统计符合条件的数量。但很快意识到这种解法的时间复杂度高达O(n^4)对于100x100的矩阵来说计算量会达到1亿次显然不可行。2. 解题思路分析2.1 暴力解法的局限性最直观的暴力解法是四重循环枚举子矩阵的左上角(i,j)枚举子矩阵的右下角(k,l)计算子矩阵[i..k][j..l]的元素和统计和等于target的数量这种解法虽然简单直接但时间复杂度太高无法通过LeetCode的测试用例。我们需要寻找更高效的算法。2.2 前缀和优化思路为了优化计算我们可以引入二维前缀和的概念。二维前缀和preSum[i][j]表示从(0,0)到(i-1,j-1)这个子矩阵的元素和。通过预处理前缀和数组我们可以在O(1)时间内计算任意子矩阵的和sum preSum[k1][l1] - preSum[i][l1] - preSum[k1][j] preSum[i][j]这样可以将时间复杂度降到O(n^4)但仍然不够高效。2.3 降维思考更进一步的优化思路是将二维问题转化为一维问题。我们可以枚举矩阵的上下边界行范围将这两行之间的列压缩成一维数组在这个一维数组上寻找子数组和等于target的数量这样就将问题转化为多次求解一维数组的子数组和问题可以使用哈希表来优化。3. 最优解法实现3.1 算法步骤详解基于上述思路最优解法的步骤如下预处理二维前缀和数组preSum枚举子矩阵的上边界row1和下边界row2计算当前行范围内每列的和形成一个一维数组colSum在这个一维数组上使用哈希表记录前缀和出现的次数遍历时维护当前前缀和currSum查找currSum-target是否在哈希表中统计所有满足条件的子矩阵数量3.2 代码实现public int numSubmatrixSumTarget(int[][] matrix, int target) { int m matrix.length, n matrix[0].length; int[][] preSum new int[m1][n1]; // 计算二维前缀和 for (int i 1; i m; i) { for (int j 1; j n; j) { preSum[i][j] preSum[i-1][j] preSum[i][j-1] - preSum[i-1][j-1] matrix[i-1][j-1]; } } int count 0; // 枚举上下边界 for (int row1 0; row1 m; row1) { for (int row2 row1; row2 m; row2) { MapInteger, Integer map new HashMap(); map.put(0, 1); // 初始前缀和为0出现1次 // 枚举右边界 for (int col 0; col n; col) { // 计算当前列的前缀和 int currSum preSum[row21][col1] - preSum[row1][col1]; // 查找满足条件的子矩阵 count map.getOrDefault(currSum - target, 0); // 更新哈希表 map.put(currSum, map.getOrDefault(currSum, 0) 1); } } } return count; }3.3 复杂度分析时间复杂度O(m²n)预处理前缀和O(mn)枚举上下边界O(m²)每对边界处理列O(n)空间复杂度O(mn)用于存储前缀和数组4. 关键点与优化技巧4.1 前缀和计算的边界处理在实现前缀和时我们通常将preSum数组定义为(m1)x(n1)大小这样可以统一处理边界情况。preSum[i][j]表示的是原矩阵中从(0,0)到(i-1,j-1)的子矩阵和。4.2 哈希表的初始状态在每次处理新的行范围时我们需要初始化哈希表并放入(0,1)这个键值对。这表示前缀和为0的情况出现了1次对应空子矩阵的情况。4.3 降维思想的运用这道题最关键的优化思路是将二维问题转化为一维问题。通过固定行范围将列压缩成一维数组然后利用一维子数组和的解法来统计结果。5. 常见问题与调试技巧5.1 为什么我的解法会超时如果直接使用四重循环的暴力解法时间复杂度为O(n^4)对于100x100的矩阵会超时。必须使用前缀和哈希表的优化方法。5.2 为什么需要初始化哈希表为(0,1)这是为了处理从第一列开始的子矩阵。如果没有这个初始化会漏掉这些情况。5.3 如何验证代码的正确性可以先用小矩阵测试比如2x2或3x3的矩阵手动计算所有可能的子矩阵和验证代码输出是否正确。5.4 如何处理矩阵中的负数哈希表的方法天然支持负数不需要特殊处理。这是这种方法的一个优势。6. 算法扩展与变种6.1 最大子矩阵和问题类似的思想可以用于解决最大子矩阵和问题。只需要将哈希表查找改为维护最小前缀和即可。6.2 三维矩阵的情况如果扩展到三维矩阵可以考虑先固定两个维度在第三个维度上使用类似的方法。不过时间复杂度会更高。6.3 多个目标值的情况如果需要同时统计多个目标值的子矩阵数量可以修改哈希表的结构记录更多信息。7. 实际应用场景这种子矩阵求和的问题在实际中有多种应用图像处理中特定模式的识别数据分析中特定区域的数据统计金融分析中特定时间段和指标的筛选游戏开发中地图区域属性的计算理解这类问题的解法可以帮助我们在面对类似的实际问题时快速找到解决方案。
