滑动窗口简介

动态维护一个区间[j, i]，使这个区间保持一个性质
其中，i可以一直往后移动，若性质丢失，则j随之往后移动，直至满足此性质
本质就是y总说的双指针维护单调性

解决问题的方式

枚举每个i，找到和i对应的j，每次更新答案

时间复杂度

双指针算法的时间复杂度
$$ O(n) $$

类似题目

1. acwing799. 最长连续不重复子序列
2. acwing61. 最长不含重复字符的子字符串
3. acwing4186. 收集雪花
4. lc1004. 最大连续1的个数 III
5. lc2024. 考试的最大困扰度
6. lc567. 字符串的排列
7. lc643. 子数组最大平均数 I
8. lc713. 乘积小于K的子数组
9. acwing4394.最长连续子序列

1. acwing799. 最长连续不重复子序列

1. 枚举右端点i
2. 维护区间[i, j]，使之不含有重复的数

#include <iostream>

using namespace std;

const int N = 100010;

int w[N], h[N];
int n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];
    int res = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        h[w[i]]++;
        while(h[w[i]] > 1)
        {
            h[w[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res;
    return 0;
}

2. acwing61. 最长不含重复字符的子字符串

维护区间[i, j]，使之不含有重复的字母

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char, int> h;
        int res = 0;
        for(int i = 0, j = 0; i < s.size(); i++) {
            h[s[i]]++;
            while(h[s[i]] > 1) {
                h[s[j]]--;
                j++;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};

3.acwing4186. 收集雪花

维护区间[i, j]，使之不含有重复的字母

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 1e6 + 10;

int w[N];
int n;

int main()
{
    cin >> n;
    int res = 0;
    for(int i = 0; i < n; i++) scanf("%d", &w[i]);
    unordered_map<int, int> h; 
    for(int i = 0, j = 0; i < n; i++)
    {
        int c = w[i];
        h[c]++;
        while(h[c] > 1)
        {
            h[w[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    cout << res;
    return 0;
}

4.lc1004. 最大连续1的个数 III

[j, i]维护区间中0的个数

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int res = 0, sum = 0;
        for(int j = 0, i = 0; i < nums.size(); i++) {
            if(nums[i] == 0) sum++;
            while(sum > k) {
                if(nums[j] == 0) sum--;
                j++;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
};

5.lc2024. 考试的最大困扰度

[j, i]维护区间内字母的数量

class Solution {
public:
    int maxAnswers(string& s, int k, char ch) {
        int sum = 0, res = 0;
        for(int i = 0, j = 0; i < s.size(); i++) {
            if(s[i] == ch) sum++;
            while(sum > k) {
                if(s[j] == ch) sum--;
                j++;
            }
            res = max(res, i - j + 1);
        }
        return res;
    }
    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(maxAnswers(answerKey, k, 'F'), maxAnswers(answerKey, k, 'T'));
    }
};

6.lc567. 字符串的排列

滑动窗口 + 哈希，判断区间[j, i]是否满足要求

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = s1.size(), n = s2.size();
        if(m > n) return false;
        unordered_map<char, int> S1, h;
        for(auto c: s1) S1[c]++;
        for(int i = 0, j = 0; i < n; i++) {
            h[s2[i]]++;
            while(j <= i && (!S1.count(s2[i]) || h[s2[i]] > S1[s2[i]])) {
                h[s2[j]]--;
                j++;
            }
            if(s1.size() == i - j + 1) return true;
        }
        return false;
    }
};

7.lc643. 子数组最大平均数 I

[i, j]维护一个长度k

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double res = -1e5, sum = 0;
        int n = nums.size();
        for(int i = 0, j = 0; i < n; i++) {
            sum += nums[i];
            if(i - j + 1 > k) {
                sum -= nums[j];
                j++;
            }
            if(i - j + 1 == k) res = max(res, sum / k);
        }
        return res;
    }
};

8.lc713. 乘积小于K的子数组

维护区间内的乘积，此处记录答案的时候可以枚举以i为结尾的子数组个数

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int res = 0, n = nums.size(), s = 1;
        for(int i = 0, j = 0; i < n; i++) {
            s *= nums[i];
            while(j <= i && s >= k) {
                s /= nums[j];
                j++;
            }
            res += i - j + 1; // [j, i]区间内，以i结尾的所有可能的结果
        }
        return res;
    }
};

9.acwing4394.最长连续子序列

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5e5 + 10, M = 1e6 + 10;

int a[N];
int n, k;
int h[M];

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int cur = 0, res = 0, fl, fr;
    for(int i = 1, j = 1; i <= n; i++)
    {
        int x = a[i];
        if(!h[x]) cur++;
        h[x]++;
        while(j <= i && cur > k)
        {
            int x = a[j];
            h[x]--;
            if(!h[x]) cur--;
            j++;
        }
        if(i - j + 1 > res)
        {
            fl = j, fr = i;
            res = i - j + 1;
        }
    }
    cout << fl << ' ' << fr;
    return 0;
}