LeetCode304. 二维区域和检索 - 矩阵不可变

秒速五厘米 2022-11-04 11:25 115阅读 0赞

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]  
示例：

给定 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable

class NumMatrix { 
    public:
        vector<vector<int>> p;
        NumMatrix(vector<vector<int>>& matrix) { 
            int m=matrix.size();
            if(m>0){ 
                int n=matrix[0].size();
                p.resize(m);
                for(int i=0;i<m;i++){ 
                    p[i].push_back(0);//0 
                    for(int j=0;j<n;j++){ 
                        int tmp=p[i][j]+matrix[i][j];
                        p[i].push_back(tmp);
                    }
                }
            }else{ 
                return;
            }
        }
        
        int sumRegion(int row1, int col1, int row2, int col2) { 
            int ans=0;
            for(int i=row1;i<=row2;i++){ 
                ans+=(p[i][col2+1]-p[i][col1]);
            }
            return ans;
        }
    };
    
    /** * Your NumMatrix object will be instantiated and called as such: * NumMatrix* obj = new NumMatrix(matrix); * int param_1 = obj->sumRegion(row1,col1,row2,col2); */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221023/1885297349f447ceb23ea33edd5aa9af.png