判断子序列

题目

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

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

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 ${a_1,a_3,a_5}$ 是序列 ${a_1,a_2,a_3,a_4,a_5}$ 的一个子序列。

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

第二行包含 $n$ 个整数，表示 $a_1,a_2,…,a_n$。

第三行包含 $m$ 个整数，表示 $b_1,b_2,…,b_m$。

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

数据范围 $1≤n≤m≤10^5,−10^9≤a_i,b_i≤10^9$ 输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

思路

维护两个指针i,j分别指向两个数组的起点，遍历中进行以下操作：

1. 当 a[i] == b[j] 时 i ++ ; j ++ ;
2. 否则 j ++ ;

注意：因为题目是要判断 $a$ 是否为 $b$ 的子序列，所以默认 $b$ 为长度大的数组，所以上面第二步要执行 j ++ ;

代码

#include <iostream>

using namespace std;

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

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 ++ ;
        // }
        // else
        //     j ++ ;
        if (a[i] == b[j]) i ++ ;
        j ++ ;
    }
    
    if (i == n) puts("Yes");
    else puts("No");
    
    return 0;
}