滑动窗口

1. 分析题意，确定窗口的意义

2. 设置窗口的left，right指针：

   （1）先移动右指针，当窗口满足条件时，记录状态；

   （2）再移动左指针，寻找下一个窗口

leetcode.1208 尽可能使字符串相等

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int res = 0;
        int n = min(s.size(), t.size());
        vector<int> cost(n, 0);
        for (int i = 0; i < n; ++i) {
            cost[i] = abs(s[i] - t[i]);
        }
        int left = 0;
        int right = 0;
        int winSum = 0;
        while (right < n) {
            winSum += cost[right];
            while (winSum > maxCost) {
                winSum -= cost[left];
                left++;
            }
            res = max(res, right - left + 1);
            right++;
        }
        return res;
    }
};

差分

一维差分

1. 定义

vector<int> nums = {1, 2, 5, 8, 13};
vector<int> diff(nums.size());
for (int i = 1; i < diff.size(); ++i) {
  diff[i] = nums[i] - nums[i-1]；
}

2. 用法

进行区间的修改，比如某区间增加或者删减一个值

对区间[x, y)增加1，则：

// [x, y)增加1
diff[x] += 1;
diff[y] -= 1;

3. 对某数组的某区间进行频繁增减操作：

   （1）先求出其对应差分数组；

   （2）对差分数组进行处理；

   （3）遍历差分数组，求前缀和，即可还原数组。

leetcode.1094 拼车

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int MAX_LEN = 1e3 + 1;
        vector<int> diff(MAX_LEN);
        for (const auto& tp: trips) {
            int nums = tp[0];
            int start = tp[1];
            int end = tp[2];
            diff[start] += nums;
            diff[end] -= nums;
        }
        int counts = 0;
        for (const auto& i: diff) {
            counts += i;
            if (counts > capacity) return false;
        }
        return true;
    }
};

前缀和

一维前缀和

vector<int> nums(n, 0); 对应的前缀和数组为:
// 长度加1
vector<int> preSum(n + 1, 0);
// 初始化
for (int i = 1; i < preSum.size(); ++i) {
    preSum[i] = preSum[i-1] + nums[i-1];
}
// 计算[i, j)区间内的子序和
// i [0, n-1], j [1, n]
int sum = preSum[j] - preSum[i]
// 以0位为第一个元素的所有区间前缀和
for (int i = 1; i < preSum.size(); ++i) {
  cout << preSum[i] - preSum[0] << endl;
}

leetcode.560 和为k的子数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> preSum(n + 1, 0);
        for (int i = 1; i < preSum.size(); ++i) {
            preSum[i] = preSum[i-1] + nums[i-1];
        }
        int res = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;
        for (int j = 1; j <= n; ++j) {
            int require = preSum[j] - k;
            if (mp.find(require) != mp.end()) {
                res += mp[require];
            }
            mp[preSum[j]]++;
        }
        return res;
};

二维差分及前缀和

https://www.cnblogs.com/LMCC1108/p/10753451.html

二维前缀和 -> leetcode.304