AcWing 2816. 判断子序列
原题链接
简单
作者:
Lyle2021
,
2021-01-20 11:22:59
,
所有人可见
,
阅读 333
1,优化前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],b[N];
int n,m;
bool as[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++){
for(j=j;j<m;j++){
if(b[j]==a[i]){
as[i]=true;
j++;
break;
}
}
if(as[i]!=true)break;
}
if(as[n-1]==true)printf("Yes");
else printf("No");
return 0;
}
2,优化后(少用一个bool数组)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],b[N];
int n,m;
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 i=0,j=0;
for(j=j;j<m;j++){
if(a[i]==b[j])i++;
if(i==n){
printf("Yes");
return 0;
}
}
printf("No");
return 0;
}