304. 二維區(qū)域和檢索 - 矩陣不可變
給定一個(gè)二維矩陣渐排，計(jì)算其子矩形范圍內(nèi)元素的總和，該子矩陣的左上角為 (row1, col1) ，右下角為 (row2, col2)。
Range Sum Query 2D
上圖子矩陣左上角 (row1, col1) = (2, 1) 炫彩，右下角(row2, col2) = (4, 3)，該子矩形內(nèi)元素的總和為 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
題解
求二維數(shù)組的前綴和体谒，求法見這位大佬。需要注意的是臼婆，我們初始化前綴和數(shù)組時(shí)抒痒，多了一行一列，使得第0行颁褂、第0列的元素也可以計(jì)算故响。
class NumMatrix {
private int[][] sum;
public NumMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return;
int rows = matrix.length;
int cols = matrix[0].length;
sum = new int[rows + 1][cols + 1];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
}
}
