一、题目
303. 区域和检索 - 数组不可变
304. 二维区域和检索 - 矩阵不可变
二、分析
- 由于最多会调用 10^4次 sumRange 方法，所以在sumRange中计算数组的区域和，时间复杂度会非常高，于是乎这道题的目的就是让在构造函数中进行一些操作，使得每次调用sumRange函数时间复杂度降下来。
本题可以通过在构造函数中求前n项和的方式，将数组a的前n项和另存到a_sum数组中。
| a[] | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| a_sum[] | 0 | 1 | 3 | 6 | 10 |
计算i~j的的数组区域和，比如计算[2~4]的数组和(闭区间)，只需要sum[4]-sum[2 - 1] = 9 = a[2] + a[3] + a[4]
- 对于矩阵，同样可以这样做，设置一个“区域和”矩阵Sum:
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]
]
则 Sum为：
Sum = [
[3, 3, 4, 8, 10],
[8, 14, 18, 24, 27],
[9, 17, 21, 28, 36],
[13, 22, 26, 34, 49],
[14, 23, 30, 38, 58]
]
则
给定一个区域：如图中的 绿色区域 ：row1, col1, -- row2, col2，该区域内矩阵的元素和为：
最外层紫色区域 - A(竖线填充区域) - B(横线填充区域) + C(A和B的交叉区域)。
按照此思路，比如row1, col1 = [1,1]; row2, col2 = [3,3]，则
a
n
s
=
S
u
m
3
,
3
−
S
u
m
3
,
0
−
S
u
m
0
,
3
+
S
u
m
0
,
0
=
34
−
13
−
8
+
3
=
16
ans=Sum_{3,3}-Sum_{3,0}-Sum_{0,3}+Sum_{0,0}=34-13-8+3=16
ans=Sum3,3−Sum3,0−Sum0,3+Sum0,0=34−13−8+3=16
Sum = [
[3, 3, 4, 8, 10],
[8, 14, 18, 24, 27],
[9, 17, 21, 28, 36],
[13, 22, 26, 34, 49],
[14, 23, 30, 38, 58]
]
但是要注意行列为0的时候，计算公式会简单一些。
三、代码
class NumArray {
public:
vector<int> sums;
NumArray(vector<int>& nums) {
int n = nums.size();
sums.resize(n + 1);
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
}
int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
};
class NumMatrix {
private:
vector<vector<int>> matSum;
public:
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if(m != 0){
int n = matrix[0].size();
matSum.resize(m, vector<int>(n));
matSum[0][0] = matrix[0][0];
// 列为0时，计算公式不同于后者
for(int i = 1; i < m; i ++){
matSum[i][0] = matSum[i-1][0] + matrix[i][0];
}
// 行为0时，计算公式也不同于后者
for(int j = 1; j < n; j ++){
matSum[0][j] = matSum[0][j-1] + matrix[0][j];
}
for(int i = 1; i < m; i ++){
for( int j = 1; j < n; j ++){
matSum[i][j] = matrix[i][j] + matSum[i-1][j] + matSum[i][j-1] -matSum[i-1][j-1];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
if(row1 == 0 && col1 == 0) return matSum[row2][col2];
if(row1 == 0 && col1 != 0) return matSum[row2][col2] - matSum[row2][col1 - 1];
if(row1 != 0 && col1 == 0) return matSum[row2][col2] - matSum[row1 - 1][col2];
return matSum[row2][col2] + matSum[row1-1][col1-1] - matSum[row2][col1-1] - matSum[row1-1][col2];
}
};
这样做完全可以，但是如果觉得三个判断很麻烦，还可以改一下Sum矩阵：
Sum = [
[0, 0, 0, 0, 0, 0]
[0, 3, 3, 4, 8, 10],
[0, 8, 14, 18, 24, 27],
[0, 9, 17, 21, 28, 36],
[0, 13, 22, 26, 34, 49],
[0, 14, 23, 30, 38, 58]
]
这样就不用判断这么多次，但是占用空间更大了，多了m+n-1个元素。
四、结果：
- 执行用时：24 ms, 在所有 C++ 提交中击败了88.74%的用户
内存消耗：16.6 MB, 在所有 C++ 提交中击败了82.85%的用户 - 执行用时：16 ms, 在所有 C++ 提交中击败了97.97%的用户
内存消耗：15 MB, 在所有 C++ 提交中击败了40.42%的用户