1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class NumMatrix {
private int[][] prefixSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
prefixSum = new int[m][n];
for (int i = 0; i < m; i++) {
int currRowSum = 0;
for (int j = 0; j < n; j++) {
currRowSum += matrix[i][j];
prefixSum[i][j] += currRowSum;
prefixSum[i][j] += i == 0 ? 0 : prefixSum[i - 1][j];
}
}
int[][] test = prefixSum;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int ans = prefixSum[row2][col2];
if (row1 > 0) {
ans -= prefixSum[row1 - 1][col2];
}
if (col1 > 0) {
ans -= prefixSum[row2][col1 - 1];
}
if (row1 > 0 && col1 > 0) {
ans += prefixSum[row1 - 1][col1 - 1];
}
return ans;
}
}
|
就是prefix sum. 如果row1和col1同时大于0, 记得把左上角区域再加回来因为它被重复减去了一次.
时间复杂度: O(m * n)对于constructor, sumRegion是O(1)
空间复杂度: O(m * n)
