labuladong数组笔记

一、前缀和数组

前缀和主要适⽤的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。 如果我们想求区间 nums[i..j] 的累加和，只要计算 preSum[j+1] - preSum[i] 即可，⽽不需要遍历整个区间求和

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

class NumArray {
public:
    NumArray(vector<int>& nums) {
        vec = nums;
    }
    int sumRange(int left, int right) {
        sum = 0;
        for (int i = left; i <= right; i++) {
            sum += vec[i];
        }
        return sum;
    }
private:
    vector<int> vec;
    int sum;
};

class NumArray {
public:
    NumArray(vector<int>& nums) {
        preSum = nums;
        int tmp = 0;
        for (int i = 0; i < preSum.size(); i++) {
            tmp += preSum[i];
            preSum[i] = tmp;
        }
    }
    int sumRange(int left, int right) {
        int sum;
        if (left > 0) {
            sum = preSum[right] - preSum[left - 1];
        }
        else sum = preSum[right];
        return sum;
    }
private:
    vector<int> preSum;
};

1.2 304. ⼆维区域和检索 - 矩阵不可变

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        preSum = matrix;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (i > 0 && j > 0) {
                    preSum[i][j] += preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1];
                }
                else if (i > 0){
                    preSum[i][j] += preSum[i - 1][j];
                }
                else if (j > 0){
                    preSum[i][j] += preSum[i][j - 1];
                }
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        if (row1 > 0 && col1 > 0) {
            sum = preSum[row2][col2] - preSum[row2][col1 - 1] - preSum[row1 - 1][col2] + preSum[row1 - 1][col1 - 1];
        }
        else if (row1 == 0 && col1 == 0) {
            sum = preSum[row2][col2];
        }
        else if (row1 > 0) {
            sum = preSum[row2][col2] - preSum[row1 - 1][col2];
        }
        else {
            sum = preSum[row2][col2] - preSum[row2][col1 - 1];
        }
        return sum;
    }
private:
    vector<vector<int>> preSum;
};

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, 0));
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                preSum[i + 1][j + 1] = matrix[i][j] + preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j];
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        sum = preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1];
        return sum;
    }
private:
    vector<vector<int>> preSum;
};

1.3 560. 和为 K 的⼦数组

// 前缀和 + 哈希表
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        map[0] = 1;
        int count = 0;
        int preSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            preSum += nums[i];
            if (map.find(preSum - k) != map.end()) {
                count += map[preSum - k];
            }
            map[preSum]++;            
        }
        return count;
    }
};

二、差分数组

差分数组的主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减 比如：输⼊⼀个数组 nums，然后⼜要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减3，再给 nums[0..4] 全部加 2

差分数组对应的概念是前缀和数组，对于数组[1,2,2,4]，其差分数组为[1,1,0,2]，差分数组的第 i个数即为原数组的第 i-1个元素和第 i 个元素的差值，也就是说我们对差分数组求前缀和即可得到原数组。

差分数组的性质是，当我们希望对原数组的某一个区间 [l,r]施加一个增量 inc 时，差分数组 d 对应的改变是：d[l] 增加 inc，d[r+1] 减少 inc。

这样对于区间的修改就变成了对于两个位置的修改。并且这种修改是可以叠加的，即当我们多次对原数组的不同区间施加不同的增量，我们只要按规则修改差分数组即可。

2.1 370. 区间加法

// 跟2.2是一模一样的

2.2 1109. 航班预订统计

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> nums(n, 0); // 该题的差分数组初始化即为0
        for (auto& booking : bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

2.3 1094. 拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> nums(1001, 0);
        for (auto& trip : trips) {
            nums[trip[1]] += trip[0];  // 注意下标
            if (trip[2] <= 1000) {
                nums[trip[2]] -= trip[0];
            }
        }
        if (nums[0] > capacity) return false;
        for (int i = 1; i < 1001; i++) {
            nums[i] += nums[i - 1];
            if (nums[i] > capacity) return false;
        }
        return true;
    }
};