一、定长滑动窗口#

模板

1
// 固定窗口大小为 k
2
    string s;
3
    // 在 s 中寻找窗口大小为 k 时的所包含最大元音字母个数
4
    int  right = 0;
5
    while(right < s.size()) {
6
        window.add(s[right]);
7
        right++;
8
        // 如果符合要求，说明窗口构造完成，
9
        if (right>=k) {
10
            // 这是已经是一个窗口了，根据条件做一些事情
11
           // ... 可以计算窗口最大值等
12
            // 最后不要忘记把 right -k 位置元素从窗口里面移除
13
        }
14
    }
15
    return res;

§1.1基础#

二、不定长滑动窗口#

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，求子数组个数。

注：滑动窗口相当于在维护一个队列。右指针的移动可以视作入队，左指针的移动可以视作出队。

不定长滑动窗口#

§2.1 越短越合法/求最长/最大#

当窗口不满足条件的时候,移动左指针

1
class Solution {
2
public:
3
    int lengthOfLongestSubstring(string s) {
4
        if(s.size() == 0) return 0;
5
        unordered_set<char> lookup;
6
        int maxStr = 0;
7
        int left = 0;
8
        for(int i = 0; i < s.size(); i++){
9
            while (lookup.find(s[i]) != lookup.end()){
10
                lookup.erase(s[left]);
11
                left ++;
12
            }
13
            maxStr = max(maxStr,i-left+1);
14
            lookup.insert(s[i]);
15
    }
16
        return maxStr;
17

18
    }
19
};

§2.1.1 基础#

§2.2 越长越合法/求最短/最小#

1
class Solution {
2
public:
3
    int minSubArrayLen(int target, vector<int>& nums) {
4
        int ans = INT_MAX;
5
        int sum = 0;
6
        int left = 0;
7
        for(int i = 0; i < nums.size(); i++){
8
            sum += nums[i];
9
            while(sum >= target){
10
                sum -= nums[left];
11
                ans = min(ans, i - left + 1);
12
                left++;
13
            }
14
        }
15
        return ans == INT_MAX ? 0 : ans;
16
    }
17
};

§2.3 求子数组个数#

§2.3.1 越短越合法#

一般要写 ans += right - left + 1。

内层循环结束后，[left,right] 这个子数组是满足题目要求的。由于子数组越短，越能满足题目要求，所以除了 [left,right]，还有 [left+1,right],[left+2,right],…,[right,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 left,left+1,left+2,…,right 的所有子数组都是满足要求的，这一共有 right−left+1 个。

1
class Solution {
2
public:
3
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
4
        if(k <= 1){
5
            return 0;
6
        }
7
        int cnt = 1;
8
        int left = 0;
9
        int ans = 0;
10
        for(int i = 0; i < nums.size(); i++){
11
            cnt *= nums[i];
12
            while(cnt >= k){
13
                cnt /= nums[left];
14
                left++;
15
            }
16
            ans += i - left + 1;
17
        }
18
        return ans;
19
    }
20
};

§2.3.2 越长越合法#

一般要写 ans += left。

内层循环结束后，[left,right] 这个子数组是不满足题目要求的，但在退出循环之前的最后一轮循环，[left−1,right] 是满足题目要求的。由于子数组越长，越能满足题目要求，所以除了 [left−1,right]，还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说，当右端点固定在 right 时，左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的，这一共有 left 个。

我们关注的是 left−1 的合法性，而不是 left。

1
class Solution {
2
public:
3
    int numberOfSubstrings(string s) {
4
        int cnt[3]{};
5
        int left = 0;
6
        int ans = 0;
7
        for(int i = 0; i < s.size(); i++){
8
            cnt[s[i] - 'a']++;
9
            while(cnt[0] && cnt[1] && cnt[2]){
10
                cnt[s[left] - 'a']--;
11
                left++;
12
            }
13
            ans += left;
14
        }
15
        return ans;
16
    }
17
};

§2.3.3 恰好型滑动窗口#

例如，要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：

计算有多少个元素和 ≥ k 的子数组。
计算有多少个元素和 > k，也就是 ≥ k + 1 的子数组。

答案就是元素和 ≥ k 的子数组个数，减去元素和 ≥ k + 1 的子数组个数。这里把 > 转换成 ≥，从而可以把滑窗逻辑封装成一个函数 solve，然后用 solve(k) - solve(k + 1) 计算，无需编写两份滑窗代码。

总结：「恰好」可以拆分成两个「至少」，也就是两个「越长越合法」的滑窗问题。

注：也可以把问题变成 ≤ k 减去 ≤ k - 1，即两个「至多」。可根据题目选择合适的变形方式。

注：也可以把两个滑动窗口合并起来，维护同一个右端点 right 和两个左端点 left_1 和 left_2，我把这种写法叫做三指针滑动窗口。

1
class Solution {
2
public:
3
    int numSubarraysWithSum(vector<int>& nums, int goal) {
4
        int ans = solve(nums, goal) - solve(nums, goal - 1);
5
        return ans;
6
    }
7
    int solve(vector<int>& nums, int k){ // <=k的子数组个数
8
        if(k < 0) return 0;
9
        int left = 0;
10
        int ans = 0;
11
        int cnt = 0;
12
        for(int i = 0; i < nums.size(); i++){
13
            cnt += nums[i];
14
            while(cnt > k){
15
                cnt -= nums[left];
16
                left++;
17
            }
18
            ans += i - left + 1;
19
        }
20
        return ans;
21
    }
22
};