双指针算法

一般结构

for(int i = 0,j = 0;i < n;i++){
    while(j < i && check(i, j)) j++;

    //每道题目的具体逻辑
}

核心用途：优化（将双重循环优化O(n^2)->O(n)）

优化方式：找单调性

eg1：输出一句话中的每一个单词

#include <iostream>
#include <string.h>
using namespace std;
int main(){
    char str[1000];
    gets(str);
    int n = strlen(str);

    for(int i = 0;i < n;i++){
        int j = i;          //指向每个单词的第一个字母
        while(j < n && str[j] != ' ') j++;      //让j指针指向每一个单词的最后一个字母

        for(int k = i;k < j;k++) cout << str[k];        //输出当前单词
        cout << endl;
        i = j;      //让i指针指向单词之间的空格，每次循环后，都会再次使i指针指向单词的第一个字母
    }
}

一、799最长连续不重复子序列

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N],s[N];      //s[N]用于存储当前区间数出现的次数

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
        scanf("%d",&q[i]);
    }

    int res = 0;
    for(int i = 1, j = 1;i <= n;i++){
        s[q[i]]++;      //统计q[i]
        while(s[q[i]] > 1){     //如果q[i]出现次数大于1，则说明当前数是出现过的
            s[q[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }

    cout << res;
    return 0;
}

二、800数组元素的目标和

#include <iostream>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll A[N],B[N];

int main(){
    int n,m,x;
    cin >> n >> m >> x;

    for(int i = 0;i < n;i++){
        scanf("%lld",&A[i]);
    }
    for(int j = 0;j < m;j++){
        scanf("%lld",&B[j]);
    }

    for(int i = 0, j = m - 1;i < n;i++){
        while(A[i] + B[j] > x) j--;
        if(A[i] + B[j] == x) cout << i << " " << j;
    }
    return 0;
}

三、2816判断子序列

#include <iostream>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
ll A[N],B[N];

int main(){
    int n,m;
    cin >> n >> m;
    int i,j;
    for(i = 0;i < n;i++) scanf("%lld",&A[i]);
    for(i = 0;i < m;i++) scanf("%lld",&B[i]);

    for(i = 0,j = 0;i < n,j<m;j++){
        if(B[j] == A[i]) i++;
        if(i == n) break;

    }
    if(i == n) {cout << "Yes";}
    else cout << "No";
    return 0;
}