1.题目描述

剑指 Offer II 013. 二维子矩阵的和

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],    [1,0,3,0,5]]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
1
2
3
4
5
6
7
8
9
10
11

2.解题思路与代码

2.1 解题思路

这道题有两种方法，第一种就是计算每一行数据的前缀和数组 sumMatrix，然后依次计算 [row1, row2] 每一行中从 [col1, col2] 之和，最后求的总和，该方法能够通过，但是在获取结果的时候依然需要按行进行遍历。所以可以考虑使用第二种方法，使用二维的前缀和数组进行解答。按照题目的要求我们需要完成两步：生成二位前缀和数组和根据二位前缀和数组求得结果

1. 生成二位前缀和数组

   我们要计算一个二维数组的二位前缀和数组，其实就是求从原点 [0, 0] 开始到 [i, j] 的矩阵内所有数字的总和，以题目示例二位数组为例，在我们计算 [1,1] 这个位置的二位前缀和数组时即求从 [0, 0] 开始到 [1, 1] 所组成矩形内的数字之和，即如图所示。同理求 [3, 2] 位置的二位前缀和数组时即求从 [0, 0] 开始到 [3, 2] 所组成矩形内的数字之和。
   
   

在计算 [3, 2] 位置的二位前缀和数组时我们可以看到如图所示的三个区域相加求得，并且需要减去重叠区域。

​ 那么我们在求 [i, j] 位置的二维前缀和时，需要该位置横向前一位 (i, j-1) 的前缀加上纵向前一位 (i-1, j) 的前缀和加，并加上传入的二维数组 [i, j] 位置的值。此时可以看到在我们计算 (i, j-1) 和 (i-1, j) 前缀和时，存在重叠部分，如图所示，而重叠部分正好是 [i-1, j-1] 的前缀和，那么就可以得到二维前缀和数组的计算公式
$$sum[i,j]=sum[i-1][j]+sum[i][j-1]+mat[i][j]-sum[i-1][j-1]$$

2. 求目标区域总和

   我们得到二维前缀和数组之后便可以求指定矩形区域内的数字总和了。题目给我们返回左上角 (row1, col1) 、右下角 (row2, col2)两个点的坐标，那么我们就可以得到行范围 [row1, row2] 和列范围 [col1, col2] 。sum[row2, col2] 是从 [0, 0] 到 [row2, col2] 范围上的总和，那么我们就需要从 sum[row2, col2] 减去多余的部分，如图所示。
   

从图中可以看出要获取蓝色背景区域综合，需要使用红框区域总和减去黄框和蓝框区域总和。减去多余部分后，存在减多的情况，即两个区域重叠部分（途中黄框和篮框重叠部分），而这个部分正好是 sum[row1, col1]所以可以得到求和公式如下：

$$sum[(row1,col1),(row2,col2)]=sum[row2][col2]-sum[row2][col1-1]-sum[row1-1][col2]+sum[row1-1][col1-1]$$

2.2 代码

class NumMatrix {
    int[][] sumMatrix;

    public NumMatrix(int[][] matrix) {
        int N = matrix.length;
        int M = matrix[0].length;
        sumMatrix = new int[N+1][M+1];
        sumMatrix[0][0] = matrix[0][0];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                sumMatrix[i+1][j+1] = sumMatrix[i][j + 1] + sumMatrix[i + 1][j] - sumMatrix[i][j] + matrix[i][j]; // 这里整体向前移了一位，方便写代码
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sumMatrix[row2+1][col2+1]-sumMatrix[row2+1][col1]-sumMatrix[row1][col2+1]+sumMatrix[row1][col1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.3 测试结果

通过测试

3.总结

• 使用二维前缀和数组解答