LeetCode 题解工作台
元素和为目标值的子矩阵数量
给出矩阵 matrix 和目标值 target ，返回元素总和等于目标值的非空子矩阵的数量。 子矩阵 x1, y1, x2, y2 是满足 x1 且 y1 的所有单元 matrix[x][y] 的集合。 如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们可以枚举矩阵的上下边界 和 ，每次算出当前上下边界内每列的元素和，记为数组 ，然后问题就转换为如何在数组 中寻找和为目标值 的子数组个数。我们累加这些子数组的个数，就是题目要求的答案。 那么题目就变成了：给定一个数组 和目标值 ，计算有多少个子数组的和为 ，我们可以通过函数 $f(nums, target)$ 来求解。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。
示例 1：
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0 输出：4 解释：四个只含 0 的 1x1 子矩阵。
示例 2：
输入：matrix = [[1,-1],[-1,1]], target = 0 输出：5 解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
示例 3：
输入：matrix = [[904]], target = 0 输出：0
提示：
1 <= matrix.length <= 1001 <= matrix[0].length <= 100-1000 <= matrix[i][j] <= 1000-10^8 <= target <= 10^8
解题思路
方法一：枚举上下边界 + 前缀和 + 哈希表
我们可以枚举矩阵的上下边界 和 ，每次算出当前上下边界内每列的元素和，记为数组 ，然后问题就转换为如何在数组 中寻找和为目标值 的子数组个数。我们累加这些子数组的个数，就是题目要求的答案。
那么题目就变成了：给定一个数组 和目标值 ，计算有多少个子数组的和为 ，我们可以通过函数 来求解。
函数 的计算方法如下：
- 定义一个哈希表 ，用来记录出现过的前缀和以及其出现次数，初始时 ；
- 初始化变量 ，其中 表示前缀和，而 表示和为 的子数组个数；
- 从左到右遍历数组 ，对于当前遍历到的元素 ，更新前缀和 ，如果 的值存在，那么更新 ，即子数组个数增加 。然后更新哈希表中元素 的值，即 ；继续遍历下一个元素；
- 遍历结束之后，返回子数组个数 。
时间复杂度 ，空间复杂度 。其中 和 分别是矩阵的行数和列数。
class Solution:
def numSubmatrixSumTarget(self, matrix: List[List[int]], target: int) -> int:
def f(nums: List[int]) -> int:
d = defaultdict(int)
d[0] = 1
cnt = s = 0
for x in nums:
s += x
cnt += d[s - target]
d[s] += 1
return cnt
m, n = len(matrix), len(matrix[0])
ans = 0
for i in range(m):
col = [0] * n
for j in range(i, m):
for k in range(n):
col[k] += matrix[j][k]
ans += f(col)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(rows^2 * cols) because each row pair iteration computes sums across columns with constant-time hash operations. Space complexity is O(cols) for the hash map per row pair, plus O(rows*cols) if using full 2D prefix sums. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Watch for the O(n^4) brute force attempt; hash map optimization is expected.
- question_mark
They may ask about transforming 2D submatrix sums into a 1D prefix sum problem.
- question_mark
Check if you recognize that cumulative sum differences allow constant-time subarray queries.
常见陷阱
外企场景- error
Not handling negative numbers in prefix sums correctly, leading to missing submatrices.
- error
Double-counting submatrices due to incorrect boundary handling.
- error
Attempting naive nested loops over all submatrices without reducing to row pairs and hash lookup.
进阶变体
外企场景- arrow_right_alt
Count submatrices where the sum is less than or equal to a target instead of exact equality.
- arrow_right_alt
Find the largest area submatrix with sum exactly equal to target.
- arrow_right_alt
Return coordinates of all submatrices summing to target instead of just the count.