题目描述

给定一个长度为 $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≤105$

$−109≤ai,bi≤109$

输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

代码&思路

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m,res=0;
int a[N],b[N];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(a[i]!=b[j]&&j<m-1)//找相同的数
        {
            j++;
        }
        if(a[i]==b[j])//找到相同的数的个数
        {
            res++;
            j++;//记得移动到下一位
        }
    }
    if(res==n)//确保相同的数与a数组的个数相同
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}