简单双指针模板

区间需要满足某种性质

同时如果这个区间不满足那么对于包含他的区间一定也是不满足

当区间的右端点增加时，左区间的移动趋势一定是增加

可以随着区间的左右端点的变化依旧维护性质,可以转移

可以用于求解满足某些要求的区间的数量

注意有些题目明显的就是具有二分性质，但是他可能也是具有双指针性质，降低时间复杂度
判断依据：左指针只会随着右指针的变大而变大，当前区间不行大的一定不行

void solve(){

    cin>>n;
    vector<int> cnt(N);
    vector<int> a(n+1);
    int ans = 0;
    for(int i=1,j=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
        while(cnt[a[i]]>1){
            cnt[a[j]]--;
            j++;
        }
        ans = max(ans,i-j+1);
    }
    cout << ans << endl;
    return ;
}

进阶双指针

考虑对于区间中满足某些要求的区间的数量
如果我们对于右端点得到了满足要求的最大的左端点，我们可以发现任意选择区间中的点得到的结果就是题目要求的<=要求的区间数量
如下 求解恰好等于数的种类恰好等于3的区间数量

恰好等于数的种类恰好等于3的区间数量 == 数的种类恰<=3的区间数量 –数的种类恰<=2的区间数量

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    auto cal = [&](int x) -> ll {
        map<int, int> m;
        ll ans = 0;
        for (int i = 1, l = 1, c = 0; i <= n; i++) {
            if (++m[a[i]] == 1) c++;
            while (c > x) {
                if (--m[a[l++]] == 0) c--;
            }
            ans += i - l + 1;
        }
        return ans;
    };
    cout << cal(3) - cal(2) << endl;
}

特别如果要求我们选择数构成序列而得到的性质与最大值和最小值有关的话可以直接排序然后双指针思考

双指针维护求解某个区间的数量

同上分析如果说后面的区间一定是不会严格包含前面的区间，同时左区间一定是呈现递增所以就可以使用双指针计算

在预处理的基础上双指针+前缀和优化要求在满足性质t的情况下区间长度至少为x

双指针和序列性质的结合

序列自动机

例题引入

(序列长度较小)
题意一般是要在字符串中需要出现某种序列,或者同时维护不出现某种序列的数量
我们可以发现同时要的就是对当前区间来随着指针的移动来维护区间的信息
注意到我们可以考虑使用序列自动机,对每一个点去维护离他最近的后一个字母所在的位置
 for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++) ne[i][j]=ne[i+1][j];
        ne[i][s[i+1]-'A']=i+1;
    }
我们由此可以固定i为左指针,用j当做快指针向后去移动类似kmp的匹配方式向后跳跃最后判断要求出字符串的位置和不出现字符串的位置

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=200010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;
//ACCEPT WA 
// 怎么表示子序列的特性
// 
int ne[N][26];
void solve(){

    cin>>n>>m;
    string s; cin>>s; s=' '+s;
    string ac ="ACCEPT",wa="WA";
    for(int i=n-1;i>=0;i--){
        for(int j=0;j<26;j++) ne[i][j]=ne[i+1][j];
        ne[i][s[i+1]-'A']=i+1;
    }
    LL ans = 0;
    for(int i=1;i<=n;i++){
        int a = i-1;
        for(auto&c:ac){
            a = ne[a][c-'A'];
            if(!a) break;
        }
        int b = i-1;
        for(auto&c:wa){
            b = ne[b][c-'A'];
            if(!b) break;
        }
        if(!a) continue;
        if(!b) b = n+1;
        a = max(a,i+m-1);
        if(b<a) continue;
        ans += b-a;
    }
    cout << ans << endl;
    return ;
}
signed main ()
{
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
         solve();
    }
}