303. 区域和检索 - 数组不可变（中等）
题目：
思路：
用前缀和记录开始到当前位置的元素和，这里前缀和数组长度n+1，presum[n+1]代表0-n的元素和
class NumArray {
public:
NumArray(vector<int>& nums) {
int n=nums.size();
presum.resize(n+1);
for(int i=1;i<=n;++i){
presum[i]=presum[i-1]+nums[i-1];
}
}
int sumRange(int left, int right) {
return presum[right+1]-presum[left];
}
vector<int> presum;
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(left,right);
*/
304. 二维区域和检索 - 矩阵不可变（中等）
题目：
思路：
前缀和数组记录[0][0]->[i][j]的所有元素和。为了方便求值，在遍历时presum[i][j]=presum[i-1][j]（原点到上边一点的矩形）+presum[i][j-1]（原点到左边一点的矩形）-presum[i-1][j-1]（原点到左上方的矩形）+matrix[i-1][j-1]（加上当前点）
然后求值时presum[row2+1][col2+1](绿色)-presum[row2+1][col1]（橙色）-presum[row1][col2+1]（蓝色）+presum[row1][col1]（粉色）
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
presum=vector<vector<int>>(m+1,vector<int>(n+1));
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
presum[i][j]=presum[i-1][j]+presum[i][j-1]-presum[i-1][j-1]+matrix[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
return presum[row2+1][col2+1]-presum[row2+1][col1]-presum[row1][col2+1]+presum[row1][col1];
}
vector<vector<int>> presum;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
560. 和为K的子数组（中等）
题目：
思路：
用哈希表记录当前的前缀和
然后在累加前缀和时，从哈希表中查找相减等于k的值，并累加其次数
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int> m;
int sum=0;
//base case，当前缀和本身==k时，会查找到0
m[0]=1;
int ret=0;
for(int i=0;i<nums.size();++i){
sum+=nums[i];
//查找与sum相减为k的位置
int other=sum-k;
if(m.count(other)>0){
ret+=m[other];
}
//累加前缀和为sum的次数
m[sum]++;
}
return ret;
}
};