[数据结构与算法]【模板题】双指针算法

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

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

【输入格式】
第一行包含整数$n$。
第二行包含$n$个整数（均在$0～10^5$范围内），表示整数序列。

【输出格式】
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

【数据范围】
$1\le n\le 10^5$

【输入样例】

5
1 2 2 3 5

【输出样例】

3

【代码】

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], s[N];//数组s记录每个数出现的次数
int n;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int res = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++;
        //不断移除左端点的数直到[j,i]内没有重复元素为止
        while (s[a[i]] > 1)
        {
            s[a[j]]--;
            j++;
        }
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}

二、AcWing 800. 数组元素的目标和

【题目描述】
给定两个升序排序的有序数组$A$和$B$，以及一个目标值$x$。
数组下标从$0$开始。
请你求出满足$A[i]+B[j]=x$的数对$(i,j)$。
数据保证有唯一解。

【输入格式】
第一行包含三个整数$n,m,x$，分别表示$A$的长度，$B$的长度以及目标值$x$。
第二行包含$n$个整数，表示数组$A$。
第三行包含$m$个整数，表示数组$B$。

【输出格式】
共一行，包含两个整数$i$和$j$。

【数据范围】
数组长度不超过$10^5$。
同一数组内元素各不相同。
$1\le 数组元素\le 10^9$

【输入样例】

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

【输出样例】

1 1

【代码】

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], b[N];
int n, m, x;

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &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\n", i, j);
            break;
        }
    }
    return 0;
}

三、AcWing 2816. 判断子序列

【题目描述】
给定一个长度为$n$的整数序列$a_1,a_2,\dots ,a_n$以及一个长度为$m$的整数序列$b_1,b_2,\dots ,b_m$。
请你判断$a$序列是否为$b$序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 { a 1 , a 3 , a 5 } \left\{ a_1,a_3,a_5\right\} {a1?,a3?,a5?}是序列 { a 1 , a 2 , a 3 , a 4 , a 5 } \left\{ a_1,a_2,a_3,a_4,a_5\right\} {a1?,a2?,a3?,a4?,a5?}的一个子序列。

【输入格式】
第一行包含两个整数$n,m$。
第二行包含$n$个整数，表示$a_1,a_2,\dots ,a_n$。
第三行包含$m$个整数，表示$b_1,b_2,\dots ,b_m$。

【输出格式】
如果$a$序列是$b$序列的子序列，输出一行Yes。
否则，输出No。

【数据范围】
$1\le n\le m\le 10^5$
$?10^9\le a_i,b_i\le 10^9$

【输入样例】

3 5
1 3 5
1 2 3 4 5

【输出样例】

Yes

【代码】

#include <iostream>
#include <cstring>
using namespace std;

const int N = 100010;
int a[N], b[N];
int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);
    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) i++;
        j++;
    }
    if (i == n) puts("Yes");
    else puts("No");
    return 0;
}