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

双指针，或者说滑动窗口、尺取法，本质是利用枚举过程中两个指针单调移动的特性，把两层循环砍成线性。关键不是背模板，而是能看出什么时候指针不用回退。

下面通过四道典型的 OJ 题，看看同向双指针在不同场景下怎么用。

唯一的雪花

链接：唯一的雪花

暴力枚举左端点，右端点往后试探，碰到重复就停。左端点右移后，右端点其实不必回退——因为刚刚扫过的区间已经知道没有重复。于是我们就可以用两个指针维护一个窗口，哈希表记录每个数的出现次数。

• 右指针 r 每进窗口就把新数的次数加一；
• 如果某个数的次数超过 1，窗口不合法，这时候左指针 l 向右移动，同时把离开窗口的数的次数减一，直到重新合法；
• 每次窗口合法时，r - l + 1 就是当前不重复子段的长度，取最大值。

#include<iostream>
#include<unordered_map>
using namespace std;

const int N = 1e6 + 10;
int a[N];

int main(){
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        
        int l = 1, r = 1;
        unordered_map<int,int> mp;
        int ret = 1;
        
        while(r <= n){
            mp[a[r]]++; // 进窗口
            while(mp[a[r]] > 1){ // 当右边界元素重复，窗口不合法
                mp[a[l++]]--; // 出窗口
            }
            ret = max(ret, r - l + 1); // 更新结果
            r++;
        }
        cout << ret << endl;
    }
    return 0;
}

逛画展

链接：逛画展

要求找一段最短的连续展览，看遍所有 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;
}