双指针滑动窗口：4 道经典题的思路拆解

2.2 逛画展

2.2.1 题目

链接：逛画展

2.2.2 算法原理

这题要求的是'最短覆盖所有画师种类的区间'，还是滑动窗口，只是判断条件从'有没有重复'换成了'种类够不够'。

窗口里一般维护两个量：

• kind：当前窗口中有多少种不同画师；
• mp[x]：画师 x 在窗口里出现了几次。

操作顺序是固定的：

• right 进窗口，某个画师第一次出现时，kind++；
• 当 kind == m，说明窗口合法，开始尝试收缩；
• left 出窗口，某个画师被缩到 0 次时，kind--，窗口失效；
• 每次窗口合法时更新答案。

这题的坑点不在窗口，而在答案怎么存。题目要输出左右端点，如果一开始就把 begin/end 都维护出来，边界会多一些；只记起点，再用长度反推终点，反而更干净。我更偏向第三种写法。

2.2.3 代码

2.2.3.1 情况一

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int n, m;
int kind; // 当前窗口不同画师量
int mp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1;
    int ret = n; // 存储最短窗口
    int begin = 1;
    int end = n;
    while(r <= n){
        if(mp[a[r]]++ == 0) // 进窗口
            kind++;
        while(kind == m) // 判断
        {
            if(ret > r - l + 1) // 更新结果
            {
                ret = r - l + 1;
                begin = l;
                end = r;
            }
            if(mp[a[l++]]-- == 1) // 出窗口
                kind--;
        }
        r++;
    }
    cout << begin << " " << end << endl;
    return 0;
}

2.2.3.2 情况二

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int n, m;
int kind; // 当前窗口不同画师量
int mp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1;
    int ret = 1e7; // 存储最短窗口
    int begin = 1;
    int end = 1;
    while(r <= n){
        if(mp[a[r]]++ == 0) // 进窗口
            kind++;
        while(kind == m) // 判断
        {
            if(ret > r - l + 1) // 更新结果
            {
                ret = r - l + 1;
                begin = l;
                end = r;
            }
            if(mp[a[l++]]-- == 1) // 出窗口
                kind--;
        }
        r++;
    }
    cout << begin << " " << end << endl;
    return 0;
}

2.2.3.3 情况三

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int n, m;
int kind; // 当前窗口不同画师量
int mp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1;
    int ret = n; // 存储最短窗口
    int begin = 1;
    while(r <= n){
        if(mp[a[r]]++ == 0) // 进窗口
            kind++;
        while(kind == m) // 判断
        {
            if(ret > r - l + 1) // 更新结果
            {
                ret = r - l + 1;
                begin = l;
            }
            if(mp[a[l++]]-- == 1) // 出窗口
                kind--;
        }
        r++;
    }
    cout << begin << " " << begin + ret - 1 << endl;
    return 0;
}

2.3 字符串

2.3.1 题目

链接：字符串

2.3.2 算法原理

这题和上一题的窗口模型很像，只是目标变成了：窗口里要覆盖 26 个小写字母。

还是老套路：

• right 向右扩；
• kind 统计当前窗口里有多少种字符；
• 当 kind == 26 时，说明窗口已经满足条件，开始收缩；
• left 缩的时候，如果某个字符次数减成 0，kind--。

这个模型写熟之后，题面变化再大，本质都差不多。真正要盯住的是'当前窗口是否已经满足条件'，而不是具体是重复、覆盖还是计数。

2.3.3 代码

#include<iostream>
using namespace std;
string s;
int mp[350]; // 统计每个小写字符出现的次数
int kind; // 窗口的元素种类

int main(){
    cin >> s;
    int l = 0, r = 0;
    int ret = 1e7;
    while(r < s.size()){
        if(mp[s[r]]++ == 0) kind++;
        while(kind == 26){
            ret = min(ret, r - l + 1);
            if(mp[s[l++]]-- == 1) kind--;
        }
        r++;
    }
    cout << ret << endl;
    return 0;
}

2.4 丢手绢

2.4.1 题目

链接：丢手绢

2.4.2 算法原理

这题和前面的窗口题不太一样，维护的是一段连续区间的和。因为是环形数组，所以会出现'当前窗口已经超过一半'的情况，判断条件就写成了 2 * k > sum。

可以这样理解：

• k 是当前窗口的区间和；
• right 往右扩时，把新边长加到 k 里；
• 一旦 2 * k > sum，说明窗口已经偏大，继续扩没有意义，应该让 left 收缩；
• 每次窗口变化后都要更新答案。

这题有个细节很容易漏：答案要更新两次。一次放在 while(2 * k > sum) 里面，用 sum - k 去尝试更新；另一次放在外面，用 k 更新。少写一个，最优解就可能丢掉。

2.4.3 代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N];

int main(){
    int n; cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    int l = 1, r = 1;
    int ret = 0;
    int k = 0;
    while(r <= n){
        k += a[r];
        while(2 * k > sum) // 用 sum - k 来更新结果
        {
            ret = max(ret, sum - k);
            k -= a[l++];
        }
        ret = max(ret, k); // 用 k 来更新结果
        r++;
    }
    cout << ret << endl;
    return 0;
}

总结

双指针最值钱的地方，不是'两个指针一起跑'，而是你能不能看出窗口状态能不能复用。最长无重复子数组、最短覆盖区间、固定种类统计、环形区间最值，这几类题的共同点都在于：右指针只增不减，左指针按需收缩，答案在窗口合法时更新。把这个套路吃透，比单纯背模板更管用。