304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

这个的话考察二维前缀和公式:

sum[i][j]=sum[i-1][j] sum[i][j-1]-sum[i-1][j-1] matrix[i-1][j-1];

自己看下图就可以自己推出来的!

代码语言：javascript复制

class NumMatrix {
    int sum[][];
    public NumMatrix(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        sum=new int[m 1][n 1];
        for(int i=1;i<=m;i  ){
                for(int j=1;j<=n;j  ){
                    sum[i][j]=sum[i-1][j] sum[i][j-1]-sum[i-1][j-1] matrix[i-1][j-1];
                }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        //因为我们元素行 列  从0开始,但是前缀和行 列从1开始,所以都得加1
        row1  ; col1  ;row2  ; col2  ;
            return sum[row2][col2]-sum[row1-1][col2]-sum[row2][col1-1] sum[row1-1][col1-1];
    }
}

matrix sum

0 人点赞