企业官网建设流程全解析

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'），就算作不同的子矩阵，因此同一组坐标范围内的矩阵只计一次，但不同位置的相同元素组合会被分别计数。

示例 1：

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 Output: 4

说明：4 个只包含 0 的 1×1 子矩阵（四个角上的 0）。

示例 2：

Input: matrix = [[1,-1],[-1,1]], target = 0 Output: 5

说明：两个 1×2 子矩阵、两个 2×1 子矩阵，加上整个 2×2 子矩阵，共 5 个和为 0 的子矩阵。

题目约束（决定了算法必须高效）：

由于矩阵元素允许为负数，本题不能使用滑动窗口求解（窗口伸缩无法在负数场景下单调判断），这一点与一维场景下 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)。

具体到本题：

1. 先固定子矩阵的左右两列边界（外层两重循环枚举i和j）；
2. 把每一行的[i, j]区间和看成一个"一维数组元素"，于是问题转化为：在这个"按行压缩出来的数组"上，统计连续若干行构成的区间和等于 target 的数量；
3. 对每一行累加得到一个不断增长的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]++，顺序保证"用当前行之前的历史前缀"去匹配，不会把同一个位置重复计入。

可以验证示例 2：matrix = [[1,-1],[-1,1]]，行内前缀和后变为[[1,0],[-1,0]]。当i=0, j=0时，逐行累加得到前缀序列1, 0，与target=0匹配的前缀sum-target=0出现 2 次（空前缀 + 第二行结束），对应"两行各自的 1×1 子矩阵和为 0 的部分"……结合所有列区间组合，最终得到 5，与预期输出一致。

四、复杂度分析

空间上最优解只需要一个容量约为行数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（一维版前缀和 + map）

560 题实现 就是本题一维版本的"标准答案"：

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[i+1][j+1] = matrix[i][j] + cumsum[i][j+1] + cumsum[i+1][j] - cumsum[i][j] // SumRegion: cumsum[row2+1][col2+1] - cumsum[row1][col2+1] - cumsum[row2+1][col1] + cumsum[row1][col1]

如果说 304 题是"二维查询版前缀和"（预处理 O(m·n)、单次查询 O(1)），那么 1074 题就是"二维计数版前缀和"（枚举边界 + 哈希表）。理解 560 题的 map 计数、304 题的容斥原理，再回头看 1074 题的"行前缀和 + 列枚举 + map 计数"三段式结构，就能把这一整类"子数组/子矩阵和等于 target"的问题串成一张知识网。

七、小结

1074 题是一道将一维前缀和技巧推广到二维的典型题目，解题主线可概括为三句话：

1. 降维：枚举左右列边界，把二维子矩阵计数拆解为若干一维连续子数组计数；
2. 差值：行内前缀和让任意列区间和变成 O(1) 减法（sum[j] - sum[i-1]）；
3. 计数：借用 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