【LeetCode】304. 二维区域和检索 - 矩阵不可变

发表于 更新于 分类于 Valine：
本文字数： 125 阅读时长 ≈ 1 分钟

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

思路

  1. 二维前缀和
  2. vector容器初始化
    • 一维 sums.resize(n+1)
    • 二维 sums.resize(m+1, vector<int>(n + 1));

拓展

  1. 二维前缀和模板 Day23 AcWing 126. 最大的和

代码

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
class NumMatrix {
public:
    vector<vector<int>> sums;
    NumMatrix(vector<vector<int>>& matrix) {

        int m = matrix.size();
        if(m>0)
        {
            int n=matrix[0].size();
            sums.resize(m+1, vector<int>(n + 1));
            for (int i = 0; i < m; i++) 
                for(int j = 0;j < n; j++)
                    sums[i+1][j+1]=matrix[i][j]+sums[i][j+1];
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int s=0;
        for(int k=col1+1;k<=col2+1;k++)
        {
            s+=sums[row2+1][k]-sums[row1][k];
        }
        return s;
    }
};