每日一题-304. 二维区域和检索 - 矩阵不可变
题目
链接
中等难度
其实leetcode的每日一题设计得还是比较精心的，昨天为一维的前缀和，今天这题可以联系到二维的前缀和。
我的提交
sumregion[(r1,c1),(r2,c2)]=presum[r2,c2]-presum[r1-1,c2]-preusum[r2,c1-1]+presum[r1-1,c1-1]
class NumMatrix {
public:
vector < vector > presum;
NumMatrix(vector>& matrix) {
if(!matrix.empty()){
int r=matrix.size();
int c=matrix[0].size();
////额外多一些空间方便设计，理解为-1行和-1列
presum.resize(r+1);
for(int i=0;i 注意点：
- 还是要注意所给矩阵为空的情况
- 为了方便设计，前缀和矩阵多个-1行和-1列的空间。实际写代码的时候题目所给矩阵和前缀和矩阵的下标要理清楚
- 二维矩阵的前缀和本质上可以理解为求固定区域的面积，注意被重复计算的那块区域
执行用时：
16 ms, 在所有 C++ 提交中击败了98.55%的用户
内存消耗：
14.9 MB, 在所有 C++ 提交中击败了84.59%的用户
官方题解
题解其实也是这种做法：
第一个为一维前缀和，就是将所取区域分成一行一行求前缀和
第二个即二维前缀和