【LBLD】小而美的算法技巧:前缀和数组
一维数组中的前缀和
class NumArray {
private:
vector<int> preSum;
public:
NumArray(vector<int>& nums) {
preSum.push_back(0);
for (int i = 1; i < nums.size()+1; i++) {
preSum.push_back(nums[i-1]+preSum[i-1]);
}
}
int sumRange(int left, int right) {
return preSum[right+1] - preSum[left];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(left,right);
*/
二维矩阵中的前缀和
class NumMatrix {
private:
vector<vector<int>> preSumMatrix;
public:
NumMatrix(vector<vector<int>>& matrix) {
// 初始化
for (int i = 0; i <= matrix.size(); i++)
{
vector<int> preSumRow;
for (int j = 0; j <= matrix[0].size(); j++) {
preSumRow.push_back(0);
}
preSumMatrix.push_back(preSumRow);
}
// 计算值
for (int i = 1; i <= matrix.size(); i++)
{
for (int j = 1; j <= matrix[0].size(); j++) {
preSumMatrix[i][j] = matrix[i-1][j-1] + preSumMatrix[i-1][j] + preSumMatrix[i][j-1] - preSumMatrix[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return preSumMatrix[row2+1][col2+1] - preSumMatrix[row2+1][col1] - preSumMatrix[row1][col2+1] + preSumMatrix[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);
*/
标签:小而,前缀,NumArray,int,nums,美的,vector,LBLD,preSum
From: https://www.cnblogs.com/yangxuanzhi/p/17278144.html