LEETCODE 1314. Matrix Block Sum 解题思路分析

题目大意：

矩阵区域和

给你一个 m * n 的矩阵 mat 和一个整数 K ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

• i - K <= r <= i + K, j - K <= c <= j + K 
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, K <= 100
• 1 <= mat[i][j] <= 100

---

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

解题思路分析：

因为题目给出的矩阵规模不大，所以本题使用暴力解是可行的。暴力解需要4层循环，前两层循环是循环矩阵的每一个点，另外两层循环是来判断矩阵内符合当前点累加对象的点。暴力解法的代码会在文章的最后给出。

我们先来看一种高效的解法。本题的实质是求矩阵内某个子矩阵内所有数值的和。对于子矩阵的取值范围，取决于返回结果当前坐标以及K值，比如当前坐标为(i, j)，那么子矩阵的范围应该是P1: (i-k, j-k)，P2: (i+k, j+k)代表的子矩阵。其中P1代表子矩阵的左上点，P2为右下点。这里需要注意两个顶点P1和P2是否在矩阵内部，也就是说，i-k和j-k应该大于等于0，同理i+k和j+k也要分别小于行数与列数。总结一下：

int p1_X = max(0, i-k);
int p1_Y = max(0, j-k);
int p2_X = min(rowCount-1, i+k);
int p2_Y = min(colCount-1, j+k);

对于求子矩阵内所有数值和的问题，我们可以采用前缀和方式求解，我们定义一个二维前缀和数组presum，presum[i][j]代表点(i, j)到(0, 0)范围内所有数字和。这类题型我在之前的文章介绍过，可以参考 LEETCODE 308. Range Sum Query 2D – Mutable 解题思路分析 这篇文章。对于任意区间内[x1, y1], [x2, y2]的数值和应该等于：

sum([x1,y1],[x2,y2]) = presum[x2][y2]
                     - presum[x1-1][y2]
                     - presum[x2][y1-1]
                     + presum[x1-1][y1-1];

如果感觉公式过于抽象，我们可以参考下图：

上图最左侧红色区域是我们想求和的区域，它的和应该等于蓝色区域减去2个黄色区域的值，而被减去的2个黄色区域存在一个橘红色重复区域（参照上图最右侧），因此还要再加上这个橘色区域即是我们想求的红色区域和。对于蓝色，黄色以及橘色区域都是前缀和数组中存在的值。

因此解题时我们需要2个步骤：

1. 首先求出前缀和数组
2. 循环矩阵每一个点，查看该点的合理子矩阵范围，利用前缀和数组求该范围内数值和。

实现代码：

public int[][] matrixBlockSum(int[][] mat, int K) {
    // 前缀和数组
    int[][] presum = new int[mat.length][mat[0].length];
    // 计算前缀和
    for(int i=0;i<mat.length;i++){
        int sum=0;
        for(int j=0;j<mat[0].length;j++){
            sum+=mat[i][j];
            presum[i][j]=sum;
            if(i>0) presum[i][j]+=presum[i-1][j];
        }
    }
    // 返回结果
    int[][] res = new int[mat.length][mat[0].length];
    // 循环每个点
    for(int i=0;i<mat.length;i++){
        for(int j=0;j<mat[0].length;j++){
            // 计算出对于该点存在的合理子矩阵范围
            int minR=Math.max(0,i-K);
            int maxR=Math.min(mat.length-1,i+K);
            int minC=Math.max(0,j-K);
            int maxC=Math.min(mat[0].length-1,j+K);
            // 利用前缀和数组计算该子矩阵内所有数字和
            res[i][j]=presum[maxR][maxC];
            if(minR>0) res[i][j]-=presum[minR-1][maxC];
            if(minC>0) res[i][j]-=presum[maxR][minC-1];
            if(minR>0&&minC>0) res[i][j]+=presum[minR-1][minC-1];
        }
    }
    return res;
}

本题解法执行时间为3ms。

Runtime: 3 ms, faster than 96.32% of Java online submissions for Matrix Block Sum.Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for Matrix Block Sum.

---

解法二：暴力解

public int[][] matrixBlockSum(int[][] mat, int K) {
    // 返回结果
    int[][] res = new int[mat.length][mat[0].length];
    // 循环每个点
    for(int i=0;i<mat.length;i++){
        for(int j=0;j<mat[0].length;j++){
            // 子矩阵数字和
            int sum=0;
            // 子矩阵合理范围
            int minR=Math.max(0,i-K);
            int maxR=Math.min(mat.length-1,i+K);
            int minC=Math.max(0,j-K);
            int maxC=Math.min(mat[0].length-1,j+K);
            // 循环子矩阵每个点，计算数字和
            for(int r=minR;r<=maxR;r++){
                for(int c=minC;c<=maxC;c++){
                    sum+=mat[r][c];
                }
            }
            // 将子矩阵的和更新至返回结果
            res[i][j]=sum;
        }
    }
    return res;
}

解法二暴力解的执行时间为75ms。

Runtime: 75 ms, faster than 45.25% of Java online submissions for Matrix Block Sum.

Memory Usage: 43.3 MB, less than 100.00% of Java online submissions for Matrix Block Sum.

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