7. 前缀和

7.1 303. 区域和检索 - 数组不可变

class NumArray {
public:
    vector<int> preSum;
    //构造前缀和
    NumArray(vector<int>& nums) {
        int n=nums.size();
        preSum.resize(n+1);
        for(int i=0;i<n;i++){
            preSum[i+1]=preSum[i]+nums[i];
        }
    }
    int sumRange(int left, int right) {
        return preSum[right+1]-preSum[left];
    }
};

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

class NumMatrix {
public:
    vector<vector<int>> preSum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m=matrix.size();
        if(m>0){
            int n=matrix[0].size(); 
            preSum.resize(m+1,vector<int>(n+1));             
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    //有重叠，注意要减去
                    preSum[i+1][j+1]=preSum[i][j+1]+preSum[i+1][j]+matrix[i][j]-preSum[i][j];
                }
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        //有重叠，注意要加回来
        return preSum[row2+1][col2+1]-preSum[row1][col2+1]-preSum[row2+1][col1]+preSum[row1][col1];
    }
};

7.3 560. 和为 K 的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //定义哈希表存放前缀和
        unordered_map<int,int> preSum;
        preSum[0]=1;
        //转换为 preSum[j]==preSum[i]-k;
        int count=0,sum_i=0;
        for(int i=0;i<nums.size();i++){
            sum_i+=nums[i];
            //nums[0...j]
            int sum_j=sum_i-k;
            //如果前边有这个前缀和，直接更新
            if(preSum[sum_j]!=0){
                count+=preSum[sum_j];
            }
            //把nums[0...i]加入preSum中
            preSum[sum_i]++;
        }
        return count;
    }
};

7.4 区间加法

#include<iostream>
#include<vector>
using namespace std;
//差分数组
class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> diff(length,0);
        for(auto &update:updates){
            int start=update[0],end=update[1],val=update[2];
            diff[start]+=val;
            if(end<length-1){
                diff[end+1]-=val;
            }
        }
        for(int i=1;i<length;i++){
            diff[i]+=diff[i-1];
        }
        return diff;
    }
};
int main(){
    int length=5;
    int n=3;
    vector<vector<int>> updates;
    vector<int> result(length,0);
    vector<int> v1;
    vector<int> v2;
    vector<int> v3;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(2);
    v2.push_back(2);
    v2.push_back(4);
    v2.push_back(3);
    v3.push_back(0);
    v3.push_back(2);
    v3.push_back(-2);
    updates.push_back(v1);
    updates.push_back(v2);
    updates.push_back(v3);
    Solution s;
    for(int i=0;i<n;i++){
        cout<<"[ ";
        for(int j=0;j<n;j++){
            cout<<updates[i][j]<<" ";
        }
        cout<<"] ";
    }
    cout<<endl;
    result=s.getModifiedArray(length,updates);
    for(int i=0;i<length;i++){
        cout<<result[i]<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}

7.5 1094. 拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> res(1001,0),diff(1001,0);
        for(auto &trip:trips){
            int val=trip[0],from=trip[1],to=trip[2];
            diff[from]+=val;
            //并不包含to，这个时候已经不在车上了
            if(to<1000){                
                diff[to]-=val;
            }
        }
        res[0]=diff[0];
        if(res[0]>capacity){
            return false;
        }
        for(int i=1;i<1001;i++){
            res[i]=diff[i]+res[i-1];
            if(res[i]>capacity){
                return false;
            }
        }
        return true;
    }
};

7.6 1109. 航班预订统计

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n,0);
        //取出每个预定记录进行计算
        for(auto& booking:bookings){
            int start=booking[0]-1;
            int end=booking[1]-1;
            int val=booking[2];
            diff[start]+=val;
            if(end<n-1){
                diff[end+1]-=val;
            }
        }
        //还原数组
        for(int i=1;i<n;i++){
            diff[i]+=diff[i-1];
        }
        return diff;
    }
};