LC 1074. 元素和为目标值的子矩阵数量
题目描述
这是 LeetCode 上的 1074. 元素和为目标值的子矩阵数量 ，难度为 困难。
给出矩阵 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：
1 | |
示例 2：1
2
3输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
示例 3：1
2输入：matrix = [[904]], target = 0
输出：0
提示：
- 1 <= matrix.length <= 100
- 1 <= matrix[0].length <= 100
- -1000 <= matrix[i] <= 1000
- -$10^8$ <= target <= $10^8$
朴素二维前缀和
从题面来看显然是一道「二维前缀和」的题目，如果你还不了解「二维前缀和」，可以看看 （题解）304. 二维区域和检索 - 矩阵不可变。本题预处理前缀和的复杂度为 $O(m * n)$。
搜索所有子矩阵需要枚举「矩形左上角」和「矩形右下角」，复杂度是 $O(m^2 * n^2)$。
因此，如果把本题当做二维前缀和模板题来做的话，整体复杂度是 $O(m^2 * n^2)$。
数据范围是 $10^2$，对应的计算量是 $10^8$，处于超时边缘，但当我们枚举「矩阵右下角」$(i,j)$ 的时候，我们只需要搜索位于 $(i,j)$ 的左上方的点 $(p,q)$ 作为「矩阵左上角」，所以其实我们是取不满 $m^2 * n^2$ 的，但仍然具有超时风险（2021/05/29 Java 测试可通过）。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public int numSubmatrixSumTarget(int[][] mat, int t) {
int n = mat.length, m = mat[0].length;
int[][] sum = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int p = 1; p <= i; p++) {
for (int q = 1; q <= j; q++) {
if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == t) ans++;
}
}
}
}
return ans;
}
}
- 时间复杂度：$O(m^2 * n^2)$
- 空间复杂度：$O(m * n)$
优化枚举 + 哈希表
上述分析是从「点」上来确定一个子矩阵，在 $n$ 和 $m$ 同阶的情况下，复杂度是 $O(n^4)$ 的。
事实上，我们能从「边」的角度来确定一个子矩阵，通过枚举三条边，然后加速找第四条边的过程，这样可以将复杂度降到 $O(n^3)$。
这个分析思路在 （题解）363. 矩形区域不超过 K 的最大数值和 详细讲过，没有印象的同学可以翻翻。这道题一定程度上是那道题的简化版，在本题我们只需要找到矩阵和为 $target$ 的值，因此只需要使用「哈希表」来记录出现过的值即可，而在 （原题）363. 矩形区域不超过 K 的最大数值和 中，我们需要找到和不超过 $k$ 的最大子矩阵，因此还涉及「有序集合 + 二分」。
具体的，我们仍然需要先预处理出一个二维前缀和。然后通过枚举确定「子矩阵的上下边界」，在将「子矩阵右边界」不断右移的过程中，把「子矩阵右边界」到「原矩阵左边界」行程的矩阵和存入哈希表（因为要统计数量，存储格式为 {“面积”:”出现次数”} ），然后通过容斥原理来找到目标的「子矩阵左边界」。
假设当前我们「子矩阵的上下边界」已经固定，当枚举到某个「子矩阵右边界」时，我们先通过二维前缀和计算出「子矩阵右边界」和「原矩阵左边界」形成的矩阵和 $cur$，由于我们希望找到矩阵和为 $target$ 的子矩阵，即希望找到一个「子矩阵左边界」使得矩阵和满足要求，这等价于从「哈希表」中找到一个 $x$，使得 $cur - x = target$，这是一个 $O(1)$ 操作。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public int numSubmatrixSumTarget(int[][] mat, int t) {
int n = mat.length, m = mat[0].length;
int[][] sum = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int ans = 0;
for (int top = 1; top <= n; top++) {
for (int bot = top; bot <= n; bot++) {
int cur = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int r = 1; r <= m; r++) {
cur = sum[bot][r] - sum[top - 1][r];
if (cur == t) ans++;
if (map.containsKey(cur - t)) ans += map.get(cur - t);
map.put(cur, map.getOrDefault(cur, 0) + 1);
}
}
}
return ans;
}
}
- 时间复杂度：$O(m * n^2)$
- 空间复杂度：$O(m * n)$
进阶
【时间复杂度】在上述解法中，我们采用的是固定上下边界，移动右边界，通过哈希表找左边界的做法，复杂度为 $O(m n^2)$；自然也能改为固定左右边界，移动下边界，通过哈希表找上边界做法，复杂度为 $O(m^2 n)$。那么我们要如何调整代码，才能最大化「哈希表」带来的优化效果呢？此时的复杂度又是多少？
【空间复杂度】我们空间复杂度的瓶颈在「二维前缀和」上，但注意到无论我们采取「固定上下边界」还是「固定左右边界」的做法，扫描原矩阵的方向都是固定的，那么是否可以不预处理「二维前缀和」呢？从而将空间复杂度降低到 $O(\max(n, m))$ 呢？
上述两问，你都可以在 （题解）363. 矩形区域不超过 K 的最大数值和 中找到答案。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1074 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
