面试题13：二维子矩阵的数字之和（Java版）

题目：输入一个二维矩阵，如何计算给定左上角坐标和右下角 坐标的子矩阵的数字之和？对于同一个二维矩阵，计算子矩阵的数 字之和的函数可能由于输入不同的坐标而被反复调用多次。例如， 输入图中的二维矩阵，以及左上角坐标为（2，1）和右下角坐标 为（4，3）的子矩阵，该函数输出8。

public class NumMatrix {

    private int[][] sums;

    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return;
        }

        // 创建一个比原矩阵行数和列数都多一行（列）的二维数组
        // 因为在这个过程中有col1 - 1和row1 - 1存在，为了保证不越界
        // 且处理起来方便一些所以二维数组上边和左边多了一行和一列
        sums = new int[matrix.length + 1][matrix[0].length + 1];
        // 将各个左上角坐标为(0,0)到右下角坐标为(i,j)的子矩阵的和预先算出来
        // 并储存到matrix这个二维数组中
        // 因为每个左上角坐标为(0,0)到右下角坐标为(i,j)的子矩阵的和
        // 等于左上角坐标为(0,0)到右下角坐标为(i - 1, j)的子矩阵的和再
        // 加上矩阵从第i行的第0列到j列的数的和rowSum
        // 又因为sums二维数组上边和左边多了一行和一列
        // 所以sums[i + 1][j + 1] = sums[i][j + 1] + rowSum;
        for (int i = 0; i < matrix.length; i++) {
            int rowSum = 0;
            for (int j = 0; j < matrix[0].length; j++) {
                rowSum += matrix[i][j];
                sums[i + 1][j + 1] = sums[i][j + 1] + rowSum;
            }
        }

    }

    // 因为求二维矩阵中的指定左上角坐标(row1,col1)和右下角坐标(row2,col2)的子矩阵的和
    // 可以转换为求左上角坐标(0,0)到右下角坐标(row2,col2)的子矩阵的和
    // 减去左上角坐标(0,0)到右下角坐标(row1 - 1, col2)矩阵的和再减去左上角坐标(0,0)到右下角
    // 坐标(row2, col - 1)矩阵的和，因为减去了两遍左上角坐标(0,0)到右下角坐标(row1 - 1,col1 - 1)矩阵
    // 的和所以需要再加上一个左上角坐标(0,0)到右下角坐标(row1 - 1,col1 - 1)矩阵的和
    // 因为sums二维数组上边和左边多了一行和一列,所以在这个坐标的基础上行和列还要加一
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row1][col2 + 1] - sums[row2 + 1][col1] + sums[row1][col1];
    }
}