双指针

通用模板：

for(int i=1,j=1;i<=n;i++){
    while(j<i&&check(i,j))j++;
    //每到题目的具体逻辑
}

核心思想:

将$O(n^2)$的朴素算法:

for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        
    }
}

通过某种性质（当$i$移动时，$j$只会向后移动或不动(单调性)），优化成$O(n)$

例：给定一个$n$项数列$s$，求最长连续不重复子序列（连续，不包含重复元素的最长子序列）的长度

分析：暴力做法：

for(int i=1;i<=n;i++){
    for(int j=1;j<=i;j++){
        if(check(j,i))ans=max(ans,i-j+1);
    }
}

通过分析可以发现，当$i$增加时，$j$一定不会减小(当$i=a，j=b$时，若$j=b-1$，则序列中有重复元素，当$i=a+1$时，$j$若减小，必然包含$s[b-1]$,则序列中必有重复元素)，因此可以使用双指针:

for(int i=1,j=1;i<=n;i++){
    while(i<=j&&check(j,i))j++;
    ans=max(ans,i-j+1);
}

再考虑$check$,不难想到，可以用数组$b$记录$[j,i]$中数组出现的个数，但这样依旧会超时，于是考虑优化。

可以发现，每次$i$增加$1$时，只有$b[s[i]]$会增加$1$，而之前已经保证$b$中每个元素都小于等于$1$，所以只用考虑$b[s[i]]$，则增加$j$之前$b[s[j]]–$,每次判断$b[s[i]]$是否为$1$,若为$1$,则$j$满足要求，记录答案。不难看出，当$b[s[i]]=1$是，$j$一定小于等于$i$，可以不用判断。

代码实现如下:

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

const int N=1e5+5;
int n;
int s[N],b[N];
int ans;

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> s[i];
    }
    for(int i=1,j=1;i<=n;i++){
        b[s[i]]++;
        while(b[s[i]]>1)b[s[j]]--,j++;
        ans=max(ans,i-j+1);
    }
    cout << ans;
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。