二维数组前缀和（JAVA）

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

暴力

双层for循环，遍历子矩阵。

前缀和算法：

class NumMatrix {
    private int sum[][];
    private int matrix[][];
    public NumMatrix(int[][] matrix) {
        this.matrix=matrix;
        int rows=matrix.length+1;
        int cols=matrix[0].length+1;
        this.sum=new int[rows][cols];
        init(cols,rows);
    }
    public void init(int cols,int rows)
    {
        for(int i=1;i
        {
            for(int j=1;j
            {
                this.sum[i][j]=this.sum[i-1][j]+this.sum[i][j-1]-this.sum[i-1][j-1]+this.matrix[i-1][j-1];
            }
        }
 
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return this.sum[row2+1][col2+1]-this.sum[row2+1][col1]-this.sum[row1][col2+1]+this.sum[row1][col1];
    }
}
 
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */