题目描述

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

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

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

样例

输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes

算法1

i与a中元素匹配，取定一个i，扫描b数组，存在相等停下，不存在相等直接跳出输出no，注意即使相等，j也必须向前走一格

时间复杂度O(n)

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N =1e5+10;
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 flag=1;
    for(int i=0,j=0;i<n;i++)
    {
        while(j<m&&a[i]!=b[j])
        {
            j++;
        }

        if(j==m)
        flag=0;
        j++;

    }
    if(flag)
    cout<<"Yes";
    else
    cout<<"No";


    return 0;
}