加载中...
1074-元素和为目标值的子矩阵数量(Number of Submatrices That Sum to Target)
发表于:2021-12-03 | 分类: 困难
字数统计: 232 | 阅读时长: 1分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/number-of-submatrices-that-sum-to-target

英文原文

Given a matrix and a target, return the number of non-empty submatrices that sum to target.

A submatrix x1, y1, x2, y2 is the set of all cells matrix[x][y] with x1 <= x <= x2 and y1 <= y <= y2.

Two submatrices (x1, y1, x2, y2) and (x1', y1', x2', y2') are different if they have some coordinate that is different: for example, if x1 != x1'.

 

Example 1:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

Example 2:

Input: matrix = [[1,-1],[-1,1]], target = 0
Output: 5
Explanation: The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

Example 3:

Input: matrix = [[904]], target = 0
Output: 0

 

Constraints:

  • 1 <= matrix.length <= 100
  • 1 <= matrix[0].length <= 100
  • -1000 <= matrix[i] <= 1000
  • -10^8 <= target <= 10^8

中文题目

给出矩阵 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 <= 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 测试可通过)。

代码:

[]
class 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)$ 操作。

image.png

代码(感谢 @ulysessweb 同学提供的其他语言代码):

[]
class 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; } }
[]
class Solution { public: int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { int n = matrix.size(), m = matrix[0].size(); vector<vector<int>> sum(n + 1, vector<int>(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] + matrix[i - 1][j - 1]; } } int ans = 0; for (int top = 1; top <= n; top++) { for (int bot = top; bot <= n; bot++) { int cur = 0; unordered_map<int, int> map; for (int r = 1; r <= m; r++) { cur = sum[bot][r] - sum[top - 1][r]; if (cur == target) ans++; if (map.count(cur - target)) ans += map[cur - target]; map[cur]++; } } } return ans; } };
  • 时间复杂度:$O(m * n^2)$
  • 空间复杂度:$O(m * n)$

进阶

  1. 【时间复杂度】在上述解法中,我们采用的是固定上下边界,移动右边界,通过哈希表找左边界的做法,复杂度为 $O(m * n^2)$;自然也能改为固定左右边界,移动下边界,通过哈希表找上边界做法,复杂度为 $O(m^2 * n)$。那么我们要如何调整代码,才能最大化「哈希表」带来的优化效果呢?此时的复杂度又是多少?

  2. 【空间复杂度】我们空间复杂度的瓶颈在「二维前缀和」上,但注意到无论我们采取「固定上下边界」还是「固定左右边界」的做法,扫描原矩阵的方向都是固定的,那么是否可以不预处理「二维前缀和」呢?从而将空间复杂度降低到 $O(\max(n, m))$ 呢?

上述两问,你都可以在 (题解)363. 矩形区域不超过 K 的最大数值和 中找到答案。


最后

如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我 和 加入我们的「组队打卡」小群 ,提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南,欢迎 star 哦 ~

统计信息

通过次数 提交次数 AC比率
18770 28048 66.9%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
1054-距离相等的条形码(Distant Barcodes)
下一篇:
1071-字符串的最大公因子(Greatest Common Divisor of Strings)
本文目录
本文目录