2025-01-24双指针

双指针算法

主要内容

双指针有很多种，第一类是两个指针在不同的序列上，比如归并排序的区间合并问题，还有一类是两个指针指向同一序列的不同位置来解决一些问题。主要遇到的是第二类。

针对第二类，一般可套用下面的模板。双指针实质上是根据问题的某种特性，比如单调性，来对朴素算法进行优化。

经典例题

A+B

/*
Input:
abs fadsa dsadsa

Output:
abs
fadsa
dsadsa
*/


#include<bits/stdc++.h>
using namespace std;

void work(){
    string s;
    getline(cin,s);

    int n=s.size();

    for(int i=0;i<n;i++){
        int j=i;
        while(j<n&&s[j]!=' ') j++;

        for(int k=i;k<j;k++) cout<<s[k];
        cout<<endl;

        i=j;
    }
}

int main(){
    work();
    return 0;
}

最长连续不重复子序列

• j表示以i结尾的最长连续不重复子序列的最左下标。

• 这里要抓住问题的单调性：当i向右走的时候，j只能向右走或者原地不动。

/*
整数在N范围内
Input:
5
1 2 2 3 5

Output:
3

*/

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N];
int s[N];//记录目前[j,i]区间内某个整数出现的次数 
int n;


void work(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];

    int mx=1;

    for(int i=0,j=0;i<n;i++){
        s[a[i]]++;
        while(s[a[i]]>1){//while(j<i&&s[a[i]]>1)
            s[a[j]]--;
            j++;
        }

        mx=max(mx,i-j+1);
    }

    cout<<mx<<endl;
}

int main(){
    work();
    return 0;
}