同向双指针：从雪花唯一性到环形最远距离

逛画展

链接：逛画展

要求找一段最短的连续展览，看遍所有 m 位画家的作品。和'字符串'那题套路一样，都是'最短包含所有种类'。当窗口内的不同画家数达到 m 时，试着收缩左侧，同时更新更短的答案。

这里有个容易踩的坑：初始化区间长度。如果直接用 n 作为最短记录 ret，但 end 却初始化为 n，在某些情况下会输出错误。下面给了三种写法，推荐第三种——只记录起点 begin 和长度 ret，结束时用 begin + ret - 1 推出终点，避免了多个变量初始化打架的问题。

方案一：同时维护 begin 和 end

#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;
}

方案二：用大数初始化 ret

#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;
}

方案三：只记起点，终点靠算（推荐）

#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;
}

字符串

链接：字符串

这题的本质和逛画展一样，只是种类固定为 26 个小写字母，窗口统计改为数组即可。

#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;
}

丢手绢

链接：丢手绢

环形道路，小朋友随机丢手绢，问最远可能距离。可以转化成：在环上选两点，它们之间较短的那条弧（顺时针或逆时针）的最大值。我们用双指针维护一段顺时针弧长 k，让 r 不断前进累加弧长。一旦 2*k > sum，说明现在顺时针弧已经超过逆时针弧，那么更优的情况可能出现在逆时针弧 sum - k 上。此时收缩左端，出窗口前用 sum - k 更新结果，出窗口后用 k 更新结果。

第一次写这种题容易被两个方向更新绕晕，其实只要记住：k 是顺时针弧，当 2*k > sum 时逆时针弧更短，所以 sum - k 可能更大；而窗口滑动过程中，每次 r 前进一步，k 本身也可能是答案。

#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){ // 顺时针弧超过半圈，用逆时针弧更新
            ret = max(ret, sum - k);
            k -= a[l++];
        }
        ret = max(ret, k); // 用顺时针弧更新
        r++;
    }
    cout << ret << endl;
    return 0;
}