LeetCode *304. 二维区域和检索 - 矩阵不可变（前缀和）

题目

提示： 你可以假设矩阵不可变。 会多次调用 sumRegion 方法。 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

思路

和上一题一样如果把计算过程放在sumRegion方法中会浪费大量时间，所以依旧用到前缀和。 二维数组中求preSum: preSum[i][j] = preSum[i − 1][j] preSum[i][j − 1] − preSum[i − 1][j − 1] matrix[i][j] 如果不明白可以去看LeetCode题解 求一部分的preSum： preSum[row2][col2] − preSum[row2][col1 − 1] − preSum[row1 − 1][col2] preSum[row1 − 1][col1 − 1]

代码语言：javascript复制

class NumMatrix {
public:
    vector<vector<int>> pre;

    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty()) return ;
        pre.resize(matrix.size()   1);
        for(int i = 0; i <= matrix.size(); i  ) {
            pre[i].resize(matrix[0].size()   1);
        }
        for (int i = 0; i < matrix.size(); i  ) {
            for (int j = 0; j < matrix[0].size(); j  ) {
                pre[i   1][j   1] = pre[i][j   1]   pre[i   1][j] - pre[i][j]   matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return pre[row2   1][col2   1] - pre[row2   1][col1] - pre[row1][col2   1]   pre[row1][col1];
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

matrix ode sum

0 人点赞