雙指標介紹

一般用于做具有單調性的，滿足某一性質的區間問題，常見的快慢指標，對撞指標，滑動視窗）貌似有些人稱之為尺取法

進入屢次被相關題目按在地上摩擦，便簡單地進行整理小結，本文僅介紹一些極其基礎的雙指標題目，可能還有錯誤，大佬輕噴

題型總結

1. 求滿足某一性質的最短/最長連續子序列
2. 字串匹配
3. 維護升序
4. 尋找滿足某一條件的點對/數值

例題分析

T1 陣列截取

以左端點為基準寫法（這個想起來比較順，但是貌似適應性不強？）
分析：
前綴和預處理
列舉遍歷列舉左端點，擴展右端點
區間和三種狀態
<k繼續擴展直到不大于k
=k繼續擴展直到不大于k（有可能后面為0呢）
> k停止擴展
答案維護：如果=k則對答案進行更新維護

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll _read()
{
    char ch=nc();
    ll sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
ll n,k;
ll R=1,Ans=-1;
const int N=2e7+10;
ll sum[N];
int main()
{
    n =_read() , k = _read();
    for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + _read();
    for(int i = 1 ; i <= n ; i ++) 
    {
        while(R < n && sum[R + 1] - sum[i - 1] <= k) R ++;
        if(sum[R] - sum[i - 1] == k)Ans = max(Ans,R - i + 1);
    }
    cout << Ans;
    return 0;
}

以右端點為基準寫法（這個寫法的話普適性比較強)
遍歷右端點
邊界：左端點<=右端點，和>k
操作：在邊界內，sum>k就一直縮小，當sum=k時更新答案

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll _read()
{
    char ch=nc();
    ll sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
ll n,k;
int R=1,Ans=-1;
const int N=2e7+10;
ll sum[N];
int main()
{
  
    n =_read() , k = _read();
    for(int i = 1 ; i <= n ; i ++) sum[i] = sum[i - 1] + _read();
    for(int i = 1,j=1; i <= n ; i ++) 
    {
        while(j<=i&& sum[i] - sum[j - 1]>k) j++;
        if(sum[i]-sum[j-1]==k)Ans=max(Ans,i-j+1);
    }
    cout << Ans;
    return 0;
}

T2 Blash數集

分析：
快慢指標，作用維護升序
哪個小移動哪個，相同兩個都移動（集合的概念無重復）
邊界：cnt達到n

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a,cnt;
const int N=1e5+10;
int q[N];
int main()
{
	int posa=1,posb=1,cnt=1;
	scanf("%lld%lld",&a,&n);
	q[1]=a;
	while(cnt<=n)
	{
		int x=q[posa]*2+1;
		int y=q[posb]*3+1;
		if(x<y)
		{
			q[++cnt]=x;
			posa++;
		}
		else if(x>y)
		{
			q[++cnt]=y;
			posb++;
		}
		else
		{
			q[++cnt]=x;
			posa++;
			posb++;
		}
	}
	printf("%lld\n",q[n]);
	return 0;
}

T3 相似的數集高級版

分析：
學長的博客
快慢指標找兩個集合交集元素個數（相等元素個數）
邊界：其中一個指標到達最后一個元素就結束所以復雜度約為O(N)
原理利用單調性，兩個集合元素單調遞增

即存在這樣關系
①A[posA]<A[posA+1]
②B[posB]<B[posB+1]
對于兩個位置的元素他們右如下關系
A[posA]<B[posB]:
A[posA]<B[posB]<B[posB+1]
操作：為了令A=B,A向右移動
A[posA]=B[posB]:
A[posA]=B[posB]<A[posA+1]
A[posA]=B[posB]<B[posB+1]
操作：維護更新答案，A,B一起向右移動（其實隨便移動一個后另外一個必定還要移動）
A[posA]>B[posB]:
B[posB]<A[posA]<A[posA+1]
操作：為了令A=B,B向右移動

T4 判斷子序列

分析：
邊界：兩個指標不越界pa<=n&&<pb<=m
以子序列為基準匹配原序列
如果相同則子序列和原序列指標同時右移動進行下一位匹配
如果不同，移動原序列

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i];
    int pa=1;
    int pb=1;
    while(pa<=n&&pb<=m)
    {
        if(a[pa]!=b[pb])pb++;
        else pa++,pb++;
    }
    if(pa==n+1)puts("Yes");
    else puts("No");
    return 0;
}

T5 最長連續不重復子序列

假的雙指標（1800+ms）
分析：
以左端點為基準（可能是我不會寫左邊的緣故）
遍歷左端點，擴展右端點直到碰到重復
更新答案（注意此時右端點是已經重復的那個），詢問下一左端點

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
bool tj[N];
int a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int l=1,r=1,ans=1;
    while(l<=n)
    {
        memset(tj,0,sizeof tj);
        while(!tj[a[r]]&&r<=n)
        {
            tj[a[r]]=1;
            r++;
        }
        ans=max(ans,r-l);
        l++;r=l;
    }
    cout<<ans;
    return 0;
}

真的雙指標（50+ms）
分析：
以右端點為基準遍歷
邊界：左端點<=右端點，包含重復
只要區間包含重復，左端點縮減，并消除標記
當不包含重復的時候更新答案

#include <iostream>

using namespace std;

const int N = 100010;
int a[N], s[N];

int main()
{
    int n = 0, res = 0;
    cin >> n;

    for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    for(int i = 0, j = 0; i < n; i ++ )//右端點
    {
        s[a[i]] ++;
        while(j <= i && s[a[i]] > 1) //不滿足條件
        {
            s[a[j]] -- ;
            j ++ ;
        }
        res = max(res, i - j + 1);
    }

    cout << res << endl;
    return 0;
}

T6 陣列元素的目標和
分別從左端和右端開始找
如果a[i]+b[j]>x j向左移動盡可能讓他變小
接下來兩種可能（等于x和小于x）
如果a[i]+b[j]==x 輸出答案
如果直接進入下一回圈，i向右移動

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll a[N],b[N];
ll n,m,x;
int main()
{
    scanf("%lld%lld%lld",&n,&m,&x);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    for(int i=0;i<m;i++)scanf("%lld",&b[i]);
    for(int i=0,j=m-1;i<n;i++)
    {
        while(j>=0&&a[i]+b[j]>x)j--;
        if(a[i]+b[j]==x)
        {
            printf("%d %d",i,j);
            break;
        }
    }
    return 0;
}

做題總結

比較通用的一個代碼結構

for(int i = 0, j = 0; i < n; i ++ )//考慮起點，都為開頭/兩端什么的
{
	//check函式一般反著寫，while回圈一直縮小邊界，直到可能為答案的區間
	//注意是可能，比如上面一些題目<和=就是可能的情況，但是更新答案只在=的時候
    while (j < i && check(i, j)) j ++ ;//注意邊界問題
    //更新答案
}

需要區分的一個情況
求滿足某一性質的最短/最長連續子序列，注意這里的連續，
區分幾個概念
子序列：從原序列中抽掉幾個元素，剩下的序列為子序列，子序列不一定連續
子序列要特別說明了才算連續
子串：字串中任取l,r他們截出來的連續字串就是子串
比較典型的就是：
最長上升子序列
我在寫這篇博客的時候瞄了眼這題，起手打了個雙指標后來發現貌似不對，這題用DP做比較好

另外：文末推薦可以看看洛谷的這篇日報：尺取法小結