給定一個二維矩陣，計算其子矩形范圍內元素的總和，該子矩陣的左上角為 (row1, col1) ，右下角為 (row2, col2) 。

上圖子矩陣左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，該子矩形內元素的總和為 8。

示例：

給定 matrix = [
[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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

解題思路

維護一個前綴和數組，公式： temp[i][j]=matrix[i][j]+temp[i-1][j]+temp[i][j-1]-temp[i-1][j-1];
根據前綴和計算區域和公式：sum=temp[row2][col2]-temp[row2][col1-1]-temp[row1-1][col2]+temp[row1][col1]

代碼

   class NumMatrix {int[][] temp;public NumMatrix(int[][] matrix) {if(matrix.length==0) return;temp=new int[matrix.length][matrix[0].length];temp[0][0]=matrix[0][0];  //計算前綴和數組for (int i = 1; i < matrix.length; i++) {temp[i][0]=temp[i-1][0]+matrix[i][0];}for (int i = 1; i < matrix[0].length; i++) {temp[0][i]=temp[0][i-1]+matrix[0][i];}for (int i = 1; i < matrix.length; i++)for (int j = 1; j < matrix[0].length; j++){
//前綴和公式temp[i][j]=matrix[i][j]+temp[i-1][j]+temp[i][j-1]-temp[i-1][j-1];}}public int sumRegion(int row1, int col1, int row2, int col2) {//區域矩陣和=temp[row2][col2]-temp[row2][col1-1]-temp[row1-1][col2]+temp[row1][col1]int leftUpRow=row1-1,leftUpcol=col1-1,sum=temp[row2][col2];if(leftUpcol>=0&&leftUpRow>=0)sum+=temp[leftUpRow][leftUpcol];if(leftUpcol>=0) sum-=temp[row2][leftUpcol];if(leftUpRow>=0) sum-=temp[leftUpRow][col2];return sum;}}/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix obj = new NumMatrix(matrix);* int param_1 = obj.sumRegion(row1,col1,row2,col2);*/