题目描述

给定两个数组，判断第一组中的各元素是否再第二组中按序放置；

样例

3 5
1 3 5
1 2 3 4 5

算法1

快慢指针 $O(n)$

因为第一组的元素比第二组少且在其中有序放置，则可以使用快慢指针法，当两指针指向元素相同时，一起向右移，否则快指针自己右移；

时间复杂度 $O(n)$

C++ 代码

#include<iostream>
using namespace std;

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

int main()
{
    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];
    int i = 0, j = 0; //i是慢指针，j是快指针；
    while(j <= m){
        if(a[i] == b[j]){     //当两指针指向元素相同时才使慢指针i右移；
            ++i;
            if(i > n){        //将此判断放在a[i] == b[i]中，可减少判断次数；
                cout<<"Yes";
                return 0;     //输出之后直接结束此程序；
            }
        }
        ++j;
    }
    cout<<"No";               //如果走到这一步说明没有成功，故可以不做判断；
    return 0;
}