题目链接: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; } };