Range Sum Query 2D - Immutable
題意：
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).
Range Sum Query 2D The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
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
Note:
You may assume that the matrix does not change. There are many calls to sumRegion function. You may assume that row1 ≤ row2 and col1 ≤ col2.
解題思路：
此為 subarray sum的變形，先組成一個sums陣列，
dp[i][j] 表示從陣列的(0,0)到(i,j)中所有元素盒。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
要減掉重複的
之後query時就只需要找出邊界，減掉後再加回重複減的即可
dp[iMax + 1][jMax + 1] - dp[iMax + 1][jMin] - dp[iMin][jMax + 1] + dp[iMin][jMin];
程式碼如下：
public class NumMatrix {
private int[][] dp;
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int rows = matrix.length;
int cols = matrix[0].length;
dp = new int[rows + 1][cols + 1];
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int iMin = Math.min(row1, row2);
int iMax = Math.max(row1, row2);
int jMin = Math.min(col1, col2);
int jMax = Math.max(col1, col2);
return dp[iMax + 1][jMax + 1] - dp[iMax + 1][jMin] - dp[iMin][jMax + 1] + dp[iMin][jMin];
}
}
// 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);