AcWing 2816. 判断子序列

题目传送门

一、题目大意

给定一个长度为 \(n\) 的整数序列 \(a_1,a_2,…,a_n\) 以及一个长度为 \(m\) 的整数序列 \(b_1,b_2,…,b_m\)。

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

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

二、算法思路

1.\(j\)指针用来扫描整个\(b\)数组，\(i\)指针用来扫描\(a\)数组。若发现\(a[i]==b[j]\)，则让\(i\)指针后移一位。

2.整个过程中，\(j\)指针不断后移，而\(i\)指针只有当匹配成功时才后移一位，若最后若\(i==n\)，则说明匹配成功。

为什么双指针做法是正确的？
整个过程中\(j\)指针不断扫描\(b\)数组并且向后移动，相当于不断给\(i\)指针所指向的\(a\)数组创建匹配的机会，只有匹配成功时\(i\)指针才会向后移动一位，当\(i==n\)时，说明全部匹配成功。

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N];
int b[N];

int main() {
    //加快输入速度
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < m; i++)cin >> b[i];

    //把i放在外边，是因为后面会用到这个变量进行判断是否走到了最后
    int i = 0;
    //单层循环(谁长循环谁)，长的那个跑快指针
    for (int j = 0; j < m; j++)
        //短的那个跑慢指针,(1)注意要控制指针不越界,(2)满足条件再走一步慢指针
        if (i < n && a[i] == b[j]) i++;

    //如果匹配成功
    if (i == n) puts("Yes");
    else puts("No");
    return 0;
}

另一种写法

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
int a[N];
int b[N];

int main() {
    //加快输入速度
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < m; i++)cin >> b[i];

    //初始化i,j
    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;
}

小结：
遍历大的，对比小的，匹配，则小的指针后移，如果小的最终到头，表示匹配成功。

三、总结

（1）同向双指针
循环长指针，每次+1，走的快
内层判断短指针是否满足条件，满足+1，走的慢

最后讨论短指针的位置,注意短指针不能越界

（2）对向双指针
一左一右对向出发
第一个指针循环左->右
while 第二个指针循环右->左 排除不匹配
如果匹配，找到答案