点这里进入->海绵宝宝的双指针全解析

左右指针

对于一维数组一个指向最左侧的指针l、一个指向最右侧的指针r，两个指针向中间移动l<=r，根据题目确定具体条件

和为S的数

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
暴力的算法就是把每一种情况都算出来，因为是有序数组所以使用双指针算法，当左右指针指向的值的和大于S时向左移动右指针，当和小于S时向右移动左指针直到找到和为S的数对或者遍历结束返回-1

快慢指针

快慢指针是指移动的步长，即每次向前移动速度的快慢。（例如，让快指针每次前移动2步，慢指针每次向前移动1步）。常被用来在O(N)时间复杂度O(1)空间复杂度的情况下。

例题

最长连续不重复子序列

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式

第一行包含整数 nn。

第二行包含 n 个整数（均在 0∼10⁵ 范围内），表示整数序列。

输出格式

共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围

1≤n≤10⁵

输入样例：

5
1 2 2 3 5

输出样例：

3

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

i 指向的是字串的右端，j 指向的是字串的左端，因为是从左到右遍历的所以对于 j 的左边的数据实际上已经算过了不需要再考虑，两个相同的元素之间字串的最大长度是两个相同元素取一个加上中间的元素个数

数组元素的目标和

给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=xA[i]+B[j]=x 的数对 (i,j)(i,j)。

数据保证有唯一解。

输入格式

第一行包含三个整数 n,m,x 分别表示 A 的长度，B 的长度以及目标值 x。

第二行包含 n 个整数，表示数组 A。

第三行包含 m 个整数，表示数组 B。

输出格式

共一行，包含两个整数 i 和 j。

数据范围

数组长度不超过 10⁵。
同一数组内元素各不相同。
1≤数组元素≤10⁹

输入样例：

4 5 6
1 2 4 7
3 4 6 8 9

输出样例：

1 1

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

int main(){
    ll n,m,x;
    cin>>n>>m>>x;
    ll a[n],b[m];
    for(ll i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<m;i++)cin>>b[i];
    ll i=0,j=m-1,sum=0;
    while(i<n&&j>=0){
        if(a[i]+b[j]>x)j--;
        else if(a[i]+b[j]<x)i++;
        else {
            cout<<i<<" "<<j<<endl;
            break;
        }
    }
    return 0;
}

判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 mm 的整数序列 b1,b2,…,bm。

请你判断 aa 序列是否为 bb 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数，表示 a1,a2,…,ana1,a2,…,an。

第三行包含 m 个整数，表示 b1,b2,…,bmb1,b2,…,bm。

输出格式

如果 a 序列是 b 序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围

1≤n≤m≤10⁵
−10⁹≤a_i,b_i≤10⁹

输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

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

int main(){
    int n,m;
    cin>>n>>m;
    int a[n],b[m];
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];
    int i=0,j=0;
    while(i<n&&j<m){
        if(a[i]==b[j]){
            i++;
            j++;
        }else {
            j++;
        }
    }
    if(i==n)cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}