Question
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Example:
Given 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
Code
public class NumMatrix {
private int[][] sum;//sum[i][j]表示matrix中以(0,0)為左上甲脏，(i - 1, j - 1)為右下的矩陣中所有元素之和
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) return;
int m = matrix.length, n = matrix[0].length;
sum = new int[m + 1][n + 1];//第一行第一列為全0董栽，以免越界檢查
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];//sum[i][j]等于matrix[i - 1][j - 1] + 以(i - 1, j)為右下的矩陣之和 + 該行從[i, 0] ~ [i, j - 1]之和事秀。以(i, j - 1)為右下的矩陣之和 - 以(i - 1, j - 1)為右下的矩陣之和即為該行從[i, 0] ~ [i, j - 1]之和嘿棘。
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
if (sum == null) return 0;
return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];
}
}
// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);
Solution
sum[i][j]表示matrix中以(0,0)為左上舰涌，(i - 1, j - 1)為右下的矩陣中所有元素之和震叮。
sum[i][j]等于matrix[i - 1][j - 1] + 以(i - 1, j)為右下的矩陣之和 + 該行從[i, 0] ~ [i, j - 1]之和琅关。以(i, j - 1)為右下的矩陣之和 - 以(i - 1, j - 1)為右下的矩陣之和即為該行從[i, 0] ~ [i, j - 1]之和至朗。
所求的區(qū)域之和 = sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1]。
