1074. 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,问有多少个非空的子矩阵使得其和正好等于 target。首先来想,这道题身为 Hard 难度,肯定不能用暴力搜索,博主之前也屡次强调过,这是一种不尊重,会惨遭 OJ 的毒打。既然是要求子矩阵之和的问题,就来想想有没有什么方法可以快速求得子矩阵之和,博主马上就联想到了之前在求子数组之和时,可以通过建立累加和数组来快速的求出任意的子数组之和。这里也可以利用相同的思路,只不过是建立的是累加和矩阵,从一维升级到了二维而已,为的就是以空间来换取时间。建立的方法比一维的稍稍复杂一些,大小为 (m+1)x(n+1),多出一位可以避免越界,然后从1开始遍历,当前位置的累加和等于上面的值加上左边的值减去左上方的值,最后加上原数组中当前位置的值,这样整个累加和矩阵就建立好了。接下来就要遍历所有子矩阵了,由于矩阵有四个端点,所以遍历是四次方的时间复杂度,不过好在有累加和矩阵,只要四个端点坐标确定了,可以在常数级的时间复杂度内求出子矩阵之和,若这个值等于 target,则结果 res 自增1即可。这个方法基本上是压线过的 OJ,多亏 OJ 仁慈,放了一马,参见代码如下:

解法一:

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int res = 0, m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> sums(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                sums[i][j] = sums[i][j - 1] + sums[i - 1][j] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (int p = 1; p <= i; ++p) {
                    for (int q = 1; q <= j; ++q) {
                        int t = sums[i][j] - sums[i][q - 1] - sums[p - 1][j] + sums[p - 1][q - 1];
                        if (t == target) ++res;
                    }
                }
            }
        }
        return res;
    }
};

上面方法其实没有太多的技巧,硬说是 Hard 的难度有些牵强,再来看一种论坛上的高分解法,一种真正符合其身价的解法。这种解法的思路在之前的 Subarray Sum Equals KMax Sum of Rectangle No Larger Than K 其实都出现过,有点 Two Sum 的影子在里面。话说 Two Sum 可是博主刷的第一道题呢,那个一个阳光明媚的下午,博主安静地坐在图书馆中,打开了心爱的小 Mac,登进了朋友推荐的 LeetCode 网站,从此便和力扣结下了不解之缘。如今已经刷了上千道题了,成了大家眼中的千条哥了。好了,打住打住,回到题目,具体的思路是,先建立每一行的累加和数组,这里其实将矩阵微积分化了,看作是多行的累加,有了行的累加和数组,就可以快速知道每一行的子数组之和了。接下来只要确定行的宽度就行了,即遍历任意两个列,它们之间的距离就是子矩阵的宽,然后新建一个 HashMap,建立子矩阵之和跟其出现次数之间的映射,初识时将 0->1 这个映射对儿加入,后面会讲原因。然后新建一个变量 cur,接下来遍历所有行,由于子矩阵的宽已经确定了,遍历不同行,就是进一步确定子矩阵的高,这样就能准确的确定一个子矩阵的范围了。先利用行的累加和数组来快速求出该行的数字之和,注意为了避免数组越界,需要判断一下i是否大于0。当前的子矩阵之和求出来后,保存在了 cur 之中,现在要看其和 target 之间的关系,cur 如果小于 target,则无事发生;若大于 target,则看 cur - target 是否存在,若存在,则表示和为 target 的子矩阵也必然存在,且个数跟和为 cur-target 的子矩阵相同,所以结果 res 可以直接加上 cur-target 的映射值。但是还有一种情况,当 cur 正好等于 target 的时候,cur-target 就为0了,这时候 HashMap 中0的映射值若为0,则就没法加上这种情况了,这就是为啥要将 0->1 这个映射对儿提前加入的原因。最后别忘了将 cur 的映射值自增1,参见代码如下:

解法二:

class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int res = 0, m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                matrix[i][j] += matrix[i][j - 1];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = i; j < n; ++j) {
                unordered_map<int, int> cntMap{{0, 1}};
                int cur = 0;
                for (int k = 0; k < m; ++k) {
                    cur += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0);
                    res += cntMap[cur - target];
                    ++cntMap[cur];
                }
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1074

类似题目:

Subarray Sum Equals K

Max Sum of Rectangle No Larger Than K

Two Sum

参考资料:

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/discuss/303750/JavaC%2B%2BPython-Find-the-Subarray-with-Target-Sum

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/discuss/303773/C%2B%2B-O(n3)-Simple-1D-Subarray-target-sum-applied-to-2D-array

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation