双指针算法首先要先考虑暴力怎么做，然后再根据一些性质加以优化到达 $O(N)$ 的时间复杂度

AcWing 799. 最长连续不重复子序列

暴力做法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int  ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++)
    {
        unordered_map<int,int> mp;
        int res=0;
        for(int j=i;j<n;j++)
        {
            mp[a[j]]++;
            if(mp[a[j]]<=1)
            {
                res++;
            }
            else break;
        }
        ans=max(res,ans);
    }
    cout<<ans;
    return 0;
}

双指针算法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int n,ans;
unordered_map<int,int> mp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0,j=0;i<n;i++)
    {
        mp[a[i]]++;
        while(j<i && mp[a[i]]>1) mp[a[j++]]--;
        ans=max(ans,i-j+1);
    }
    cout<<ans;
    return 0;
}

AcWing 800. 数组元素的目标和

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int N=1e5+10;
int a[N],b[N];
int l,r;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>m>>q;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<m;i++) cin>>b[i];

    for(int i=0,j=m-1;i<n;i++)
    {
        while(j>=0 && a[i]+b[j]>q) j--;
        if(a[i]+b[j]==q) 
        {
            l=i,r=j;
        }
    }
    cout<<l<<" "<<r;
    return 0;
}

AcWing 2816. 判断子序列

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n,m;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int j=0;j<m;j++) cin>>b[j];

    int i=0,j=0;

    while(i<n && j<m)
    {
        if(a[i] == b[j]) i++;
        j++;
    }
    if(i==n) cout<<"Yes";
    else cout<<"No";
    return 0;
} 

AcWing 1238. 日志统计

暴力做法

双指针问题对于我这种菜鸟是根本想不到的，所以只能打个暴力在OI赛制里面骗分…

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct S{
    int t,id;
    bool operator<(const S&r) const {
        if(t!=r.t) return t<r.t;
    }
}s[N];
int n,d,k;
int cnt[N];
bool st[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>d>>k;
    for(int i=0;i<n;i++)
    {
        int t,id;
        cin>>t>>id;
        s[i]={t,id};
    }
    sort(s,s+n);

    for(int i=0;i<n;i++)
    {
        memset(cnt,0,sizeof cnt);
        for(int j=i;j<n;j++)
        {
           if(s[j].t-s[i].t<d)
           {

               cnt[s[j].id]++;

               if(cnt[s[j].id]>=k)
               st[s[j].id]=true;
           }
           else break;
        }
    }
    for(int i=0;i<100000;i++)
    if(st[i])
    cout<<i<<endl;
    return 0;
}

双指针算法

双指针在于找到一定的规律，当i往后走的时候如果j一直不动其实时间上是没有意义的，因为会超过d，所以在时间上超过d之后，由于整个时间段结构体存储的时间是递增的，所以j也需要往后走，走的同时，把前面的cnt[s[j].id]–,j++ ,如果时间段符合再判断是否大于等于k，成立则标记st数组

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct S{
    int t,id;
    bool operator<(const S&r) const {
        if(t!=r.t) return t<r.t;
    }
}s[N];
int n,d,k;
int cnt[N];
bool st[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>n>>d>>k;
    for(int i=0;i<n;i++)
    {
        int t,id;
        cin>>t>>id;
        s[i]={t,id};
    }
    sort(s,s+n);

    for(int i=0,j=0;i<n;i++)
    {
        cnt[s[i].id]++;
        while(s[i].t-s[j].t>=d)
        {
            cnt[s[j].id]--;
            j++;
        }
        if(cnt[s[i].id]>=k) st[s[i].id]=true;
    }
    for(int i=0;i<100000;i++)
    if(st[i])
    cout<<i<<endl;
    return 0;
}

AcWing 1240. 完全二叉树的权值

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n;
ll a[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin >>a[i];

    ll w=-1e9;
    ll depth=0;

    for(int i=1,d=1;i<=n;i*=2,d++)
    {
        ll x=0;
        for(int j=i;j<i+ (1<<(d-1)) &&j<=n ;j++)
        {
            x+=a[j];
        }
        if(x>w)
        {
            w=x;
            depth=d;
        }
    }
    cout<<depth;
    return 0;
}