双指针算法（c++）

基本思想

将for(int i = 0; i < n; i++)
for(j = 0; j <n; j++)
时间复杂度O（n^2）优化到O（n）

基本模板来自yxc

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

    // 具体问题的逻辑
}
//常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
1
2
3
4
5
6
7
8
9

经典例题

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

输入格式
第一行包含整数n。

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

输出格式
共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。

数据范围
1≤n≤100000
输入样例：

5
1 2 2 3 5
1
2

输出样例：

3
1

解答
目的：找出最长的不包含重复数字的连续区间，输出它的长度

i不断向右移动的同时，判断[j,i]区间是否有重复元素，若有则将j向右移动,并且要减去a[j] 的个数; 否则j 的位置不变

#include <iostream>
using namespace std;
const int N = 100010;

int n;
int a[N], s[N];//s[N] 用来记录每个数出现多少次
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    int res = 0;//最后连续不重复序列个数
    for(int i = 0, j = 0; i < n; i++)
    {
        s[a[i]]++;//计算a[i]个数
        while(s[a[i]] > 1)
        {
            s[a[j]] -- ;//剔除a[i] 重复时 a[j] 的数量
            j++;
        }
        res = max(res, i - j + 1);//比较找出的连续不重复数列的长度，找出最长的为最后的结果
    }
    cout << res << endl;
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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。

数据范围
数组长度不超过100000。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：

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

输出样例：

1 1
1

解答
i在第一个数组中的最左端向右移，j在第二个数组的最右端向左移动，在保证j >= 0 并且a[i] + b[j] > x 时，j 向左移动，当a[i] + b[i] == x 时满足条件输出（i, j）

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m, x;
int a[N], b[N];

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 -- ;//保证j >= 0 并且a[i] + b[j] > x 时，j 向左移动
        if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

AcWing 2816. 判断子序列
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

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

输入格式
第一行包含两个整数 n,m。

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

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

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

否则，输出 No。

数据范围
1≤n≤m≤10⁵,
−10⁹≤ai,bi≤10⁹
输入样例：

3 5
1 3 5
1 2 3 4 5
1
2
3

输出样例：

Yes
1

1. i指针用来扫描整个b数组，j指针用来扫描a数组。若发现a[j]==b[i]，则让j指针后移一位。
2. 整个过程中，i指针不断后移，而j指针只有当匹配成功时才后移一位，若最后j==n，则说明匹配成功。

整个过程中i指针不断扫描b数组并且向后移动，相当于不断给j指针所指向的a数组创建匹配的机会，只有匹配成功时j指针才会向后移动一位，当j==n时，说明全部匹配成功。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 0;i < n; i++) scanf("%d",&a[i]);
    for(int j = 0;j < m; j++) scanf("%d",&b[j]);

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22