算法总结—双指针

· · 算法·理论

双指针

双指针用于答案往都具有单调性的题目，而且我们枚举 l,r 时，通常一个 l 只会对应一个 r 。\ 二双指针又分为两种：\ ① 快慢指针：求解区间答案。\ ② 左右指针：比如二分。\ 往往双指针的题目都可以用二分写出来，但反过来就不一定了。

例题

1 连续自然数和

一道模板题。

我们把 l 设为慢指针， r 设为快指针， l 初始设为 1 , r 初始设为 0 。

实现步骤

图解 (n=15) 红色为 l 指针，黑色为 r 指针

![](https://cdn.luogu.com.cn/upload/image_hosting/unus4sxc.png) 找到了一组答案，$l$ 加一。 ![](https://cdn.luogu.com.cn/upload/image_hosting/ehoi53dc.png) 我们会发现 $l=4$ 是才会有答案。 ![](https://cdn.luogu.com.cn/upload/image_hosting/b7bnmbyu.png) 找到了一组答案，$l$ 加一，不过 $l=7$ 是才会有一组答案。 ![](https://cdn.luogu.com.cn/upload/image_hosting/d75w29cv.png) ### $\text{Code} 
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int l=1,r=0;
    int cnt=0;
    while(r<n){
        while(r<n&&cnt+(r+1)<=n){//试探性的往cnt上加上r+1
            r++; 
            cnt+=r;
        }
        if(cnt==n&&l<r){//合法，l<r不能少
            cout<<l<<" "<<r<<endl;
        }
        cnt-=l;
        l++;
    }
    return 0;
}

2 逛画展

我们把加和的过程改为桶记录有多少种画，然后 cnt++ 就可以了，记住只有第一次出现某一种画才 cnt++ 哦，因为 cnt 记录的是当前区间一共有多少种画。

\text{Code}

#include<iostream>
using namespace std;
int a[1000005];
int vis[2005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int l=1,r=0;
    int cnt=0;
    int ansl,ansr;
    int Min=1e9;
    while(r<n){
        while(r<n&&cnt<m){
            r++;
            vis[a[r]]++;
            if(vis[a[r]]==1){
                cnt++;
            }
        }
        while(cnt==m){
            if(Min>r-l+1){
                Min=r-l+1;
                ansl=l,ansr=r;
            }
            vis[a[l]]--;
            if(vis[a[l]]==0){
                cnt--;
            }
            l++;
        }
    }
    cout<<ansl<<" "<<ansr;
    return 0;
}

3 单词背诵

套路一样，不过要注意的是本题的桶存的是字符串，所以要用 map 。

\text{Code}

#include<iostream>
#include<map> 
using namespace std;
map<string,int>ma,vis;//ma是记录每种要背的单词在文章中出现了多少次，vis和上一题的意义一样
string a[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        ma[s]=1;
    }
    int m;
    cin>>m;
    int ans1=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        if(ma[a[i]]==1){
            ma[a[i]]++;
            ans1++;
        }
    }
    cout<<ans1<<endl;
    if(ans1==0){
        cout<<0;
        return 0;
    }
    int l=1,r=0;
    int Min=1e9;
    int cnt=0;//与上题一样cnt记录单词种类
    while(r<m){
        while(r<m&&cnt<ans1){
            r++;
            if(ma[a[r]]>0){
                vis[a[r]]++;
                if(vis[a[r]]==1){
                    cnt++;
                }
            }
        }
        while(cnt==ans1){
            Min=min(Min,r-l+1);
            vis[a[l]]--;
            if(ma[a[l]]!=0&&vis[a[l]]==0){//区间中没有这个单词了且文章中有这个单词
                cnt--;
            }
            l++;
        }
    }
    cout<<Min;
    return 0;
}

4 \text{Cow Lineup S}

首先我们先要对每头奶牛的顺序排个序，接着把双指针的模板套上去，不过这题的答案变为了 x_r-x_l 的最大值。\ 记得这道题要用结构体，因为排序时奶牛的编号也要变。

\text{Code}

#include<iostream>
#include<map> 
#include<algorithm>
using namespace std;
struct node{
    int x,id;
}a[50005];
bool cmp(node q,node h){
    return q.x<h.x; 
}
map<int,int>ma,vis;
int main(){
    int n;
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].id;
        ma[a[i].id]++;
        if(ma[a[i].id]==1){
            cnt++;

        }
    }
    sort(a+1,a+1+n,cmp);
    int l=1,r=0;
    int cnt1=0;
    int Min=1e9;
    while(r<n){
        while(r<n&&cnt1<cnt){
            r++;
            vis[a[r].id]++;
            if(vis[a[r].id]==1){
                cnt1++;
            }
        }
        while(cnt==cnt1){
            Min=min(Min,a[r].x-a[l].x);
            vis[a[l].id]--;
            if(vis[a[l].id]==0){
                cnt1--;
            }
            l++;
        }
    }
    cout<<Min;
    return 0;
}

5 生日礼物

这题和上题几乎一样，只是一个点上可能有多个珠子。所以我们只用把一个点分为多个位置处理即可，也只有输入变了而已。

\text{Code}

#include<iostream>
#include<map> 
#include<algorithm>
using namespace std;
struct node{
    int x,id;
}a[1000005];
bool cmp(node q,node h){
    return q.x<h.x; 
}
map<int,int>ma,vis;
int main(){
    int n,m;
    cin>>n>>m;
    int cnt=0;
    int k=0;
    for(int i=1;i<=m;i++){
        int t;
        cin>>t;
        for(int j=1;j<=t;j++){
            k++;
            cin>>a[k].x;
            a[k].id=i;
        }
    }
    sort(a+1,a+1+n,cmp);
    int l=1,r=0;
    int cnt1=0;
    int Min=1e9;
    while(r<n){
        while(r<n&&cnt1<m){
            r++;
            vis[a[r].id]++;
            if(vis[a[r].id]==1){
                cnt1++;
            }
        }
        while(m==cnt1&&l<r){
            Min=min(Min,a[r].x-a[l].x);
            vis[a[l].id]--;
            if(vis[a[l].id]==0){
                cnt1--;
            }
            l++;
        }
    }
    cout<<Min;
    return 0;
}

6 \text{Vasya and String}

由于我们不知道是改 \tt a 更优还是改 \tt b 更优，所以 \tt a,b 都得跑一遍。

我们以改为 \tt a 来举例：

首先 l=1,r=0 ，然后 r 不停加一，如果 s_r=\ 'b\ ' ,计数器加一，直到计数器大于 k 为止。接着从 r 往后找，看后面还有没有连着的 \tt a 在此过程中 r 也要加加，(关于此操作的目的，加设我们有一个字符串 "\tt aaabaa" 此时 r 跑到 4 且 k 正好用完，如果无此操作，最大答案就会变成 3 而有了这个操作后，就会避免一些跑到一个 \tt b 后，k 正好用完，且后面有 \tt a 而导致的答案错误)，最后打擂台求最大值，并且 l 加一。

\text{Code}

#include<iostream>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    int len=s.size();
    s=" "+s;
    int l=1,r=0;
    int cnt=0;
    int Max=-1e9;
    while(r<n){
        while(r<n&&cnt<k){
            r++;
            cnt+=(s[r]=='b');
        }
        while(r<n&&s[r+1]=='a'){
            r++;
        }
        Max=max(Max,r-l+1);
        if(s[l]=='b'){
            cnt--;
        }
        l++;
    }
    l=1,r=0;
    cnt=0;
    while(r<n){
        while(r<n&&cnt<k){
            r++;
            cnt+=(s[r]=='a');
        }
        while(r<n&&s[r+1]=='b'){
            r++;
        }
        Max=max(Max,r-l+1);
        if(s[l]=='a'){
            cnt--;
        }
        l++;
    }
    cout<<Max;
    return 0;
}