力扣刷题之二维区域和检索 - 矩阵不可变

题目链接:https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

这个是

区域和检索 - 数组不可变的进阶。

这道题的解题思路是分别求一维数组的前缀和,然后再求二位数组中指定区域的和。

具体实现方面,创建 m 行 n+1 列的二维数组sums,其中 m和 n分别是矩阵matrix 的行数和列数,sums[i] 为matrix[i] 的前缀和数组。将sums 的列数设为n+1 的目的是为了方便计算每一行的子数组和,不需要对 col1​ =0 的情况特殊处理。

c++代码如下:

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,vector<int>(n+1));
            for(int i=0;i<m;i++)
            {
                //计算每一行的前缀和
                for(int j=0;j<n;j++)
                    sums[i][j+1]=sums[i][j]+matrix[i][j];
            }
        }

    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum=0;
        //按行计算指定区域和并相加得到最终结果
        for(int i=row1;i<=row2;i++)
            sum+=sums[i][col2+1]-sums[i][col1];
        return sum;

    }
};

 

上一篇:AT4434 [ARC103D] Distance Sums


下一篇:Leetcode 304. 二维区域和检索 - 矩阵不可变