2021-10-02 昨天搬家断更了

今天做了几个数组的题，掌握使用前缀和。

题目如下：

解题如下：

 class NumMatrix {

    private int[][] pre_sum;

    public static void main(String[] args) {
        NumMatrix numMatrix = new NumMatrix(new int[][]{{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}});
        System.out.println(numMatrix.sumRegion(1, 0, 2, 2));

    }

    public NumMatrix(int[][] matrix) {

        this.pre_sum = matrix;

        //计算前缀和,初始化
        for (int i = 0; i < matrix.length; i++) {
            pre_sum[i][0] = matrix[i][0];
            for (int j = 1; j < matrix[i].length; j++) {
                pre_sum[i][j] = pre_sum[i][j - 1] + matrix[i][j];
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        //计算出子矩阵的元素的和

        //前缀和数组
        int[][] pre_sum = this.pre_sum;

        int sum = 0;

        for (int i = row1; i <= row2; i++) {
            if (col1 == 0) {
                sum += pre_sum[i][col2];
            } else
                //一行行计算
                sum += pre_sum[i][col2] - pre_sum[i][col1 - 1];
        }
        return sum;
    }

}