X

LEETCODE 1074. Number of Submatrices That Sum to Target解题思路分析

题目大意:

元素和为目标值的子矩阵数量

给出矩阵 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 子矩阵。

提示:

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


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1074

解题思路分析:

虽然这是一道Hard难度的题目,但之前如果做过 LeetCode 560 Subarray Sum Equals K 的话,应该会有一些灵感,本题是 Subarray Sum Equals K 的2D升级版,如果对本题没有思路,我强烈建议大家先看下之前的文章,LEETCODE 560. Subarray Sum Equals K 解题思路分析

本题也需要使用到presum思路来解题,只不过这个前缀和presum的计算对象是二维数组。对于任意一个点,presum[i][j]代表了从Matrix[0][0]到Matrix[i][j]之间的和。

有了前缀和之后,我们可以将二维数组拆解为多个一维数组,再用一维数组的思路去解题。

拆分数组时可以以列拆分,也可以以行拆,无论如何都可以达到遍历所有子矩阵的效果。本题以列拆分为例,对于任意两列col1和col2,我们可以得到所有行的前缀和

for(int row = 0; row < matrix.length; row++){
    // 计算每一行matrix[0][col1]到matrix[row][col2]间的和
    int sum_row = presum[row][col2] - presum[row][col1 - 1];
}

这样,二维数组就转化为了一维数组。接下来只要遍历所有列的组合即可。

for(int col1 = 0; col1 < matrix[0].length; col1++) {
    for(int col2 = col1; col2 < matrix[0].length; col2++) {
        ...
    }
}

本题解法时间复杂度为n的3次方。看下完整代码:

public int numSubmatrixSumTarget(int[][] matrix, int target) {
    int rowLength = matrix.length, colLength=matrix[0].length;
    int[][] presum = new int[rowLength][colLength]; // 计算前缀和
    int res=0; // 返回结果
    for(int row=0;row<rowLength;row++){
        int rowSum=0;
        for(int col=0;col<colLength;col++){
            rowSum+=matrix[row][col];
            presum[row][col] = rowSum + (row>0 ? presum[row-1][col] : 0);
        }
    }

    for(int c1 = 0; c1 < colLength; c1++){ // 循环起始列
        for(int c2 = c1; c2 < colLength; c2++){ // 循环终点列
            Map<Integer, Integer> map = new HashMap<>(); // 用于记录前缀和个数
            for(int r=0;r<rowLength;r++){ // 循环每一行
                // Matrix[0][c1]到Matrix[r][c2]见的和
                int sum = presum[r][c2]-(c1 > 0 ? presum[r][c1-1] : 0);
                if(sum == target){ // sum等于target,结果加一
                    res++;
                }
                if(map.containsKey(sum - target)){ // map中存在sum - target
                    res+=map.get(sum - target); // 将个数加入到结果
                }
                int count = map.getOrDefault(sum, 0);
                map.put(sum, count+1); // 更新当前sum的个数
            }
        }
    }
    return res;
}

本解法用时839 ms。

Runtime: 839 ms, faster than 62.33% of Java online submissions for Number of Submatrices That Sum to Target.

Memory Usage: 52.5 MB, less than 100.00% of Java online submissions for Number of Submatrices That Sum to Target.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1074-number-of-submatrices-that-sum-to-target解题思路分析/
Categories: leetcode
kwantong: