尧图网站建设 
LeetCode-Go 题解1074. Number of Submatrices That Sum to Target 子矩阵和等于目标值的计数问题【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 1074. Number of Submatrices That Sum to Target 的题解文档为骨架深入讲解统计元素总和恰好等于 target 的非空子矩阵数量这一经典二维前缀和 哈希表计数问题。文章将完整还原从 O(n⁶) 暴力枚举到 O(n³) 最优解的三步演进思路逐行剖析仓库内 Go 实现并结合测试用例与同源题目第 560 题、第 304 题说明其通用套路。读完后你不仅能用 Go 快速 AC 本题还能掌握把二维问题拍扁成一维、再用前缀和差值 map 计数的可复用算法思维。一、题目回顾子矩阵的定义与计数要求题目给定一个matrix和一个目标值target要求返回元素总和等于 target 的非空子矩阵的数量。子矩阵(x1, y1, x2, y2)定义为满足x1 x x2且y1 y y2的所有单元matrix[y][x]的集合。两个子矩阵只要有一个坐标不同例如x1 ! x1就算作不同的子矩阵因此同一组坐标范围内的矩阵只计一次但不同位置的相同元素组合会被分别计数。示例 1Input: matrix [[0,1,0],[1,1,1],[0,1,0]], target 0 Output: 4说明4 个只包含 0 的 1×1 子矩阵四个角上的 0。示例 2Input: matrix [[1,-1],[-1,1]], target 0 Output: 5说明两个 1×2 子矩阵、两个 2×1 子矩阵加上整个 2×2 子矩阵共 5 个和为 0 的子矩阵。题目约束决定了算法必须高效约束项范围matrix.length行数 m1 m 300matrix[0].length列数 n1 n 300矩阵元素matrix[i]-1000 matrix[i] 1000存在负数目标值target-10^8 target 10^8由于矩阵元素允许为负数本题不能使用滑动窗口求解窗口伸缩无法在负数场景下单调判断这一点与一维场景下 0560.Subarray-Sum-Equals-K 的结论一致。矩阵规模 300×300任何 O(n⁶) 级别的枚举都会超时必须借助前缀和与哈希表做降维。二、思路演进从 O(n⁶) 暴力到 O(n³) 最优解题解文档给出了一条清晰的优化主线仓库源码中恰好保留了三个版本的实现可以一一对照。1. O(n⁶) 纯暴力四重边界 二重求和超时最直接的想法枚举子矩阵的上下左右四条边界4 层循环再对内部所有元素求和2 层循环判断是否等于 target。对应源码中的numSubmatrixSumTarget2实现源码// 暴力解法超时 O(n^6) func numSubmatrixSumTarget2(matrix [][]int, target int) int { res : 0 for startx : 0; startx len(matrix); startx { for starty : 0; starty len(matrix[startx]); starty { for endx : startx; endx len(matrix); endx { for endy : starty; endy len(matrix[startx]); endy { if sumSubmatrix(matrix, startx, starty, endx, endy) target { res } } } } } return res }其中sumSubmatrix用双层循环累加区间内所有元素。300×300 的矩阵下O(n⁶) 的复杂度完全不可接受源码注释也直接标注暴力解法超时。这一版的意义在于验证题意、作为正确性参照。2. 一维化 Two Sum 思想拍扁为连续子数组问题题解文档的关键洞察是这道题是滑动窗口/前缀和问题的二维版本。如果能把矩阵拍扁成一维数组那么求连续子数组和为 target 的个数就非常好做——这正是第 560 题的做法。那么如何拍扁呢联想 LeetCode 第 1 题 Two Sum 的思想用哈希表保存遍历过程中出现过的累加和通过当前前缀和 - 目标值在表中查是否存在从而把求和问题优化到 O(n)。具体到本题先固定子矩阵的左右两列边界外层两重循环枚举i和j把每一行的[i, j]区间和看成一个一维数组元素于是问题转化为在这个按行压缩出来的数组上统计连续若干行构成的区间和等于 target 的数量对每一行累加得到一个不断增长的sum用map记录历史上出现过的累加和及其出现次数res counterMap[sum-target]即可统计以当前行为结尾、和为 target 的连续行区间个数。这里有一个题解文档特别强调的疑问点为什么不能每一行单独保存和而要始终用累加和相减原因在于题目要求统计所有子矩阵包括纵向拼接形成的大矩阵。例如两个 1×4 的子矩阵摞在一起形成一个 2×4 的子矩阵如果只单独保存每一行的和就需要额外的组合步骤才能拼出大矩阵而用累加和相减的方式天然覆盖了任意高度区间的组合不需要再增加一层循环。这正是map中累积前缀和的优势。这一版对应源码中的numSubmatrixSumTarget1实现源码复杂度为 O(n⁴)// 暴力解法 O(n^4) func numSubmatrixSumTarget1(matrix [][]int, target int) int { m, n, res, sum : len(matrix), len(matrix[0]), 0, 0 for i : 0; i n; i { for j : i; j n; j { counterMap : map[int]int{} counterMap[0] 1 // 题目保证一定有解所以这里初始化是 1 sum 0 for row : 0; row m; row { for k : i; k j; k { sum matrix[row][k] } res counterMap[sum-target] counterMap[sum] } } } return res }注意内层for k : i; k j; k每次重新累加当前行的列区间导致多出 O(n) 的开销整体 O(n⁴)。按题解文档的说明这一版可以 AC但时间复杂度仍然偏高。3. 行方向前缀和列维度被拍扁成 O(1) 取值O(n³)最后一处优化来自前缀和preSum。题解文档给出核心公式sum[i, j] sum[j] - sum[i - 1]其中sum[k]保存从第 0 列到第 k 列的累加和。由于是闭区间要求区间[i, j]的和需要用右边界j的累加和减去左边界 i 左边那个位置即i-1的累加和。先在每一行内部计算行方向的前缀和那么任意行上列区间[i, j]的和就可以在 O(1) 时间内得到matrix[row][j] - matrix[row][i-1] 当 i 0 时经过这一步列方向的维度被彻底拍扁给定左右列边界后每一行只需要一次减法就能得到该行在区间内的和于是问题退化为标准的一维连续子数组和为 target计数问题即 Two Sum 的变体外层两重循环枚举左右列边界O(n²)内层按行扫描O(n)维护累加和sum与哈希表counterMap每次res counterMap[sum-target]完成计数。最终总时间复杂度O(n³)。计算前缀和直接原地修改原矩阵原地用matrix[row][col] matrix[row][col-1]因此空间上只需要一个 O(n) 的哈希表。三、最优解源码逐行解析仓库中最终采用的 O(n³) 实现为numSubmatrixSumTarget实现源码完整代码如下package leetcode func numSubmatrixSumTarget(matrix [][]int, target int) int { m, n, res : len(matrix), len(matrix[0]), 0 for row : range matrix { for col : 1; col len(matrix[row]); col { matrix[row][col] matrix[row][col-1] } } for i : 0; i n; i { for j : i; j n; j { counterMap, sum : make(map[int]int, m), 0 counterMap[0] 1 // 题目保证一定有解所以这里初始化是 1 for row : 0; row m; row { if i 0 { sum matrix[row][j] - matrix[row][i-1] } else { sum matrix[row][j] } res counterMap[sum-target] counterMap[sum] } } } return res }逐段拆解第一步行内前缀和原地修改for row : range matrix { for col : 1; col len(matrix[row]); col { matrix[row][col] matrix[row][col-1] } }将每一行改造成前缀和数组matrix[row][col]从此表示该行第 0 列到第 col 列的累加和。原地修改省去额外空间同时这也意味着传入的matrix会被改写若调用方需要保留原矩阵应传入副本。第二步枚举左右列边界for i : 0; i n; i { for j : i; j n; j {i是左边界j是右边界j从i开始保证列区间非空。这一层决定了整体复杂度的 O(n²) 部分。第三步哈希表 前缀和差值计数counterMap, sum : make(map[int]int, m), 0 counterMap[0] 1 // 题目保证一定有解所以这里初始化是 1 for row : 0; row m; row { if i 0 { sum matrix[row][j] - matrix[row][i-1] } else { sum matrix[row][j] } res counterMap[sum-target] counterMap[sum] }sum表示从第 0 行到当前行、且列区间为[i, j]的子矩阵和它由每一行的列区间和累加而来每一行的列区间和通过matrix[row][j] - matrix[row][i-1]在 O(1) 内得到i 0时即matrix[row][j]特判避免数组越界counterMap[0] 1是初始化哨兵表示前缀和为 0 已经出现过一次这样当sum target时counterMap[sum-target] counterMap[0] 1能正确统计从第 0 行开始的子矩阵即空前缀的补集源码注释也点明题目保证一定有解所以这里初始化是 1每次先res counterMap[sum-target]再counterMap[sum]顺序保证用当前行之前的历史前缀去匹配不会把同一个位置重复计入。可以验证示例 2matrix [[1,-1],[-1,1]]行内前缀和后变为[[1,0],[-1,0]]。当i0, j0时逐行累加得到前缀序列1, 0与target0匹配的前缀sum-target0出现 2 次空前缀 第二行结束对应两行各自的 1×1 子矩阵和为 0 的部分……结合所有列区间组合最终得到 5与预期输出一致。四、复杂度分析版本时间复杂度空间复杂度说明numSubmatrixSumTarget2纯暴力O(n⁶)O(1)四重边界 二重求和超时numSubmatrixSumTarget1列区间内重算和O(n⁴)O(n)能 AC但行区间和需重新累加numSubmatrixSumTarget行前缀和优化O(n³)O(n)最终方案行区间和 O(1) 获取空间上最优解只需要一个容量约为行数m的哈希表make(map[int]int, m)预分配容量减少扩容前缀和直接写在原数组上因此总空间复杂度为 O(n)这里 n 指列数实际受min(m, n)约束因为列区间枚举按列数 n 进行。需要说明的是枚举左右列边界是 O(n²) 的固有开销。若将行列转置行数更少时以行枚举边界理论上可以进一步压低常数但量级仍为 O(n³)仓库实现按列枚举代码简洁直观300×300 的数据规模下完全足够。五、测试用例与运行验证仓库为本题提供了完整测试测试文件覆盖了题目给出的两个示例func Test_Problem1074(t *testing.T) { qs : []question1074{ { para1074{[][]int{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, 0}, ans1074{4}, }, { para1074{[][]int{{1, -1}, {-1, 1}}, 0}, ans1074{5}, }, } ... }测试中同时调用了三个版本的实现numSubmatrixSumTarget、numSubmatrixSumTarget1、numSubmatrixSumTarget2即 O(n³)、O(n⁴)、O(n⁶) 三种写法对同一组用例输出一致互相印证正确性。本地验证方式# 在仓库根目录执行运行 1074 题的测试 go test -v -run Test_Problem1074 ./leetcode/1074.Number-of-Submatrices-That-Sum-to-Target/项目根目录的go.mod定义了模块依赖gotest.sh提供了批量测试脚本也可以直接go test ./leetcode/...全量验证。六、同源题目把一维套路推广到二维题解文档在结尾点出了两道同思路题目仓库中均有完整实现可供对照学习第 560 题 Subarray Sum Equals K一维版前缀和 map560 题实现 就是本题一维版本的标准答案func subarraySum(nums []int, k int) int { count, pre : 0, 0 m : map[int]int{} m[0] 1 for i : 0; i len(nums); i { pre nums[i] if _, ok : m[pre-k]; ok { count m[pre-k] } m[pre] 1 } return count }它同样以m[0] 1作为哨兵count m[pre-k]完成匹配。对比可见1074 题的外层列区间枚举本质上就是对每一组左右边界重复执行 560 题的一维算法只是把nums[i]换成了第 i 行的列区间和。第 304 题 Range Sum Query 2D - Immutable二维前缀和304 题实现 是二维前缀和的经典应用用容斥原理在 O(1) 内求任意矩形区域和cumsum[i1][j1] matrix[i][j] cumsum[i][j1] cumsum[i1][j] - cumsum[i][j] // SumRegion: cumsum[row21][col21] - cumsum[row1][col21] - cumsum[row21][col1] cumsum[row1][col1]如果说 304 题是二维查询版前缀和预处理 O(m·n)、单次查询 O(1)那么 1074 题就是二维计数版前缀和枚举边界 哈希表。理解 560 题的 map 计数、304 题的容斥原理再回头看 1074 题的行前缀和 列枚举 map 计数三段式结构就能把这一整类子数组/子矩阵和等于 target的问题串成一张知识网。七、小结1074 题是一道将一维前缀和技巧推广到二维的典型题目解题主线可概括为三句话降维枚举左右列边界把二维子矩阵计数拆解为若干一维连续子数组计数差值行内前缀和让任意列区间和变成 O(1) 减法sum[j] - sum[i-1]计数借用 Two Sum 的 map 思想counterMap[sum-target]把匹配从 O(n²) 压缩到 O(n)。配合 题解文档、最优实现 与 测试用例你可以完整对照三种复杂度的代码理解每一步优化的动机与代价。掌握这道题之后遇到任何统计满足和条件的子矩阵/子数组个数类问题都可以先思考能否用前缀和 哈希表把枚举代价降下来——这正是本题留给读者的最大价值。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：1074. Number of Submatrices That Sum to Target 子矩阵和等于目标值的计数问题
LeetCode-Go 题解1074. Number of Submatrices That Sum to Target 子矩阵和等于目标值的计数问题【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode-Go 仓库中 1074. Number of Submatrices That Sum to Target 的题解文档为骨架深入讲解统计元素总和恰好等于 target 的非空子矩阵数量这一经典二维前缀和 哈希表计数问题。文章将完整还原从 O(n⁶) 暴力枚举到 O(n³) 最优解的三步演进思路逐行剖析仓库内 Go 实现并结合测试用例与同源题目第 560 题、第 304 题说明其通用套路。读完后你不仅能用 Go 快速 AC 本题还能掌握把二维问题拍扁成一维、再用前缀和差值 map 计数的可复用算法思维。一、题目回顾子矩阵的定义与计数要求题目给定一个matrix和一个目标值target要求返回元素总和等于 target 的非空子矩阵的数量。子矩阵(x1, y1, x2, y2)定义为满足x1 x x2且y1 y y2的所有单元matrix[y][x]的集合。两个子矩阵只要有一个坐标不同例如x1 ! x1就算作不同的子矩阵因此同一组坐标范围内的矩阵只计一次但不同位置的相同元素组合会被分别计数。示例 1Input: matrix [[0,1,0],[1,1,1],[0,1,0]], target 0 Output: 4说明4 个只包含 0 的 1×1 子矩阵四个角上的 0。示例 2Input: matrix [[1,-1],[-1,1]], target 0 Output: 5说明两个 1×2 子矩阵、两个 2×1 子矩阵加上整个 2×2 子矩阵共 5 个和为 0 的子矩阵。题目约束决定了算法必须高效约束项范围matrix.length行数 m1 m 300matrix[0].length列数 n1 n 300矩阵元素matrix[i]-1000 matrix[i] 1000存在负数目标值target-10^8 target 10^8由于矩阵元素允许为负数本题不能使用滑动窗口求解窗口伸缩无法在负数场景下单调判断这一点与一维场景下 0560.Subarray-Sum-Equals-K 的结论一致。矩阵规模 300×300任何 O(n⁶) 级别的枚举都会超时必须借助前缀和与哈希表做降维。二、思路演进从 O(n⁶) 暴力到 O(n³) 最优解题解文档给出了一条清晰的优化主线仓库源码中恰好保留了三个版本的实现可以一一对照。1. O(n⁶) 纯暴力四重边界 二重求和超时最直接的想法枚举子矩阵的上下左右四条边界4 层循环再对内部所有元素求和2 层循环判断是否等于 target。对应源码中的numSubmatrixSumTarget2实现源码// 暴力解法超时 O(n^6) func numSubmatrixSumTarget2(matrix [][]int, target int) int { res : 0 for startx : 0; startx len(matrix); startx { for starty : 0; starty len(matrix[startx]); starty { for endx : startx; endx len(matrix); endx { for endy : starty; endy len(matrix[startx]); endy { if sumSubmatrix(matrix, startx, starty, endx, endy) target { res } } } } } return res }其中sumSubmatrix用双层循环累加区间内所有元素。300×300 的矩阵下O(n⁶) 的复杂度完全不可接受源码注释也直接标注暴力解法超时。这一版的意义在于验证题意、作为正确性参照。2. 一维化 Two Sum 思想拍扁为连续子数组问题题解文档的关键洞察是这道题是滑动窗口/前缀和问题的二维版本。如果能把矩阵拍扁成一维数组那么求连续子数组和为 target 的个数就非常好做——这正是第 560 题的做法。那么如何拍扁呢联想 LeetCode 第 1 题 Two Sum 的思想用哈希表保存遍历过程中出现过的累加和通过当前前缀和 - 目标值在表中查是否存在从而把求和问题优化到 O(n)。具体到本题先固定子矩阵的左右两列边界外层两重循环枚举i和j把每一行的[i, j]区间和看成一个一维数组元素于是问题转化为在这个按行压缩出来的数组上统计连续若干行构成的区间和等于 target 的数量对每一行累加得到一个不断增长的sum用map记录历史上出现过的累加和及其出现次数res counterMap[sum-target]即可统计以当前行为结尾、和为 target 的连续行区间个数。这里有一个题解文档特别强调的疑问点为什么不能每一行单独保存和而要始终用累加和相减原因在于题目要求统计所有子矩阵包括纵向拼接形成的大矩阵。例如两个 1×4 的子矩阵摞在一起形成一个 2×4 的子矩阵如果只单独保存每一行的和就需要额外的组合步骤才能拼出大矩阵而用累加和相减的方式天然覆盖了任意高度区间的组合不需要再增加一层循环。这正是map中累积前缀和的优势。这一版对应源码中的numSubmatrixSumTarget1实现源码复杂度为 O(n⁴)// 暴力解法 O(n^4) func numSubmatrixSumTarget1(matrix [][]int, target int) int { m, n, res, sum : len(matrix), len(matrix[0]), 0, 0 for i : 0; i n; i { for j : i; j n; j { counterMap : map[int]int{} counterMap[0] 1 // 题目保证一定有解所以这里初始化是 1 sum 0 for row : 0; row m; row { for k : i; k j; k { sum matrix[row][k] } res counterMap[sum-target] counterMap[sum] } } } return res }注意内层for k : i; k j; k每次重新累加当前行的列区间导致多出 O(n) 的开销整体 O(n⁴)。按题解文档的说明这一版可以 AC但时间复杂度仍然偏高。3. 行方向前缀和列维度被拍扁成 O(1) 取值O(n³)最后一处优化来自前缀和preSum。题解文档给出核心公式sum[i, j] sum[j] - sum[i - 1]其中sum[k]保存从第 0 列到第 k 列的累加和。由于是闭区间要求区间[i, j]的和需要用右边界j的累加和减去左边界 i 左边那个位置即i-1的累加和。先在每一行内部计算行方向的前缀和那么任意行上列区间[i, j]的和就可以在 O(1) 时间内得到matrix[row][j] - matrix[row][i-1] 当 i 0 时经过这一步列方向的维度被彻底拍扁给定左右列边界后每一行只需要一次减法就能得到该行在区间内的和于是问题退化为标准的一维连续子数组和为 target计数问题即 Two Sum 的变体外层两重循环枚举左右列边界O(n²)内层按行扫描O(n)维护累加和sum与哈希表counterMap每次res counterMap[sum-target]完成计数。最终总时间复杂度O(n³)。计算前缀和直接原地修改原矩阵原地用matrix[row][col] matrix[row][col-1]因此空间上只需要一个 O(n) 的哈希表。三、最优解源码逐行解析仓库中最终采用的 O(n³) 实现为numSubmatrixSumTarget实现源码完整代码如下package leetcode func numSubmatrixSumTarget(matrix [][]int, target int) int { m, n, res : len(matrix), len(matrix[0]), 0 for row : range matrix { for col : 1; col len(matrix[row]); col { matrix[row][col] matrix[row][col-1] } } for i : 0; i n; i { for j : i; j n; j { counterMap, sum : make(map[int]int, m), 0 counterMap[0] 1 // 题目保证一定有解所以这里初始化是 1 for row : 0; row m; row { if i 0 { sum matrix[row][j] - matrix[row][i-1] } else { sum matrix[row][j] } res counterMap[sum-target] counterMap[sum] } } } return res }逐段拆解第一步行内前缀和原地修改for row : range matrix { for col : 1; col len(matrix[row]); col { matrix[row][col] matrix[row][col-1] } }将每一行改造成前缀和数组matrix[row][col]从此表示该行第 0 列到第 col 列的累加和。原地修改省去额外空间同时这也意味着传入的matrix会被改写若调用方需要保留原矩阵应传入副本。第二步枚举左右列边界for i : 0; i n; i { for j : i; j n; j {i是左边界j是右边界j从i开始保证列区间非空。这一层决定了整体复杂度的 O(n²) 部分。第三步哈希表 前缀和差值计数counterMap, sum : make(map[int]int, m), 0 counterMap[0] 1 // 题目保证一定有解所以这里初始化是 1 for row : 0; row m; row { if i 0 { sum matrix[row][j] - matrix[row][i-1] } else { sum matrix[row][j] } res counterMap[sum-target] counterMap[sum] }sum表示从第 0 行到当前行、且列区间为[i, j]的子矩阵和它由每一行的列区间和累加而来每一行的列区间和通过matrix[row][j] - matrix[row][i-1]在 O(1) 内得到i 0时即matrix[row][j]特判避免数组越界counterMap[0] 1是初始化哨兵表示前缀和为 0 已经出现过一次这样当sum target时counterMap[sum-target] counterMap[0] 1能正确统计从第 0 行开始的子矩阵即空前缀的补集源码注释也点明题目保证一定有解所以这里初始化是 1每次先res counterMap[sum-target]再counterMap[sum]顺序保证用当前行之前的历史前缀去匹配不会把同一个位置重复计入。可以验证示例 2matrix [[1,-1],[-1,1]]行内前缀和后变为[[1,0],[-1,0]]。当i0, j0时逐行累加得到前缀序列1, 0与target0匹配的前缀sum-target0出现 2 次空前缀 第二行结束对应两行各自的 1×1 子矩阵和为 0 的部分……结合所有列区间组合最终得到 5与预期输出一致。四、复杂度分析版本时间复杂度空间复杂度说明numSubmatrixSumTarget2纯暴力O(n⁶)O(1)四重边界 二重求和超时numSubmatrixSumTarget1列区间内重算和O(n⁴)O(n)能 AC但行区间和需重新累加numSubmatrixSumTarget行前缀和优化O(n³)O(n)最终方案行区间和 O(1) 获取空间上最优解只需要一个容量约为行数m的哈希表make(map[int]int, m)预分配容量减少扩容前缀和直接写在原数组上因此总空间复杂度为 O(n)这里 n 指列数实际受min(m, n)约束因为列区间枚举按列数 n 进行。需要说明的是枚举左右列边界是 O(n²) 的固有开销。若将行列转置行数更少时以行枚举边界理论上可以进一步压低常数但量级仍为 O(n³)仓库实现按列枚举代码简洁直观300×300 的数据规模下完全足够。五、测试用例与运行验证仓库为本题提供了完整测试测试文件覆盖了题目给出的两个示例func Test_Problem1074(t *testing.T) { qs : []question1074{ { para1074{[][]int{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, 0}, ans1074{4}, }, { para1074{[][]int{{1, -1}, {-1, 1}}, 0}, ans1074{5}, }, } ... }测试中同时调用了三个版本的实现numSubmatrixSumTarget、numSubmatrixSumTarget1、numSubmatrixSumTarget2即 O(n³)、O(n⁴)、O(n⁶) 三种写法对同一组用例输出一致互相印证正确性。本地验证方式# 在仓库根目录执行运行 1074 题的测试 go test -v -run Test_Problem1074 ./leetcode/1074.Number-of-Submatrices-That-Sum-to-Target/项目根目录的go.mod定义了模块依赖gotest.sh提供了批量测试脚本也可以直接go test ./leetcode/...全量验证。六、同源题目把一维套路推广到二维题解文档在结尾点出了两道同思路题目仓库中均有完整实现可供对照学习第 560 题 Subarray Sum Equals K一维版前缀和 map560 题实现 就是本题一维版本的标准答案func subarraySum(nums []int, k int) int { count, pre : 0, 0 m : map[int]int{} m[0] 1 for i : 0; i len(nums); i { pre nums[i] if _, ok : m[pre-k]; ok { count m[pre-k] } m[pre] 1 } return count }它同样以m[0] 1作为哨兵count m[pre-k]完成匹配。对比可见1074 题的外层列区间枚举本质上就是对每一组左右边界重复执行 560 题的一维算法只是把nums[i]换成了第 i 行的列区间和。第 304 题 Range Sum Query 2D - Immutable二维前缀和304 题实现 是二维前缀和的经典应用用容斥原理在 O(1) 内求任意矩形区域和cumsum[i1][j1] matrix[i][j] cumsum[i][j1] cumsum[i1][j] - cumsum[i][j] // SumRegion: cumsum[row21][col21] - cumsum[row1][col21] - cumsum[row21][col1] cumsum[row1][col1]如果说 304 题是二维查询版前缀和预处理 O(m·n)、单次查询 O(1)那么 1074 题就是二维计数版前缀和枚举边界 哈希表。理解 560 题的 map 计数、304 题的容斥原理再回头看 1074 题的行前缀和 列枚举 map 计数三段式结构就能把这一整类子数组/子矩阵和等于 target的问题串成一张知识网。七、小结1074 题是一道将一维前缀和技巧推广到二维的典型题目解题主线可概括为三句话降维枚举左右列边界把二维子矩阵计数拆解为若干一维连续子数组计数差值行内前缀和让任意列区间和变成 O(1) 减法sum[j] - sum[i-1]计数借用 Two Sum 的 map 思想counterMap[sum-target]把匹配从 O(n²) 压缩到 O(n)。配合 题解文档、最优实现 与 测试用例你可以完整对照三种复杂度的代码理解每一步优化的动机与代价。掌握这道题之后遇到任何统计满足和条件的子矩阵/子数组个数类问题都可以先思考能否用前缀和 哈希表把枚举代价降下来——这正是本题留给读者的最大价值。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考