算法1
(双指针法) $O(n+m)$
i扫描a串,j扫描b串,每次从b串找到a串的一个字符匹配,j就递增.
时间复杂度
a串长n,b串长m,由于每个字符仅扫描一次故时间复杂度是$O(n+m)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for(int i = 0; i < n; ++i) cin >> a[i];
for(int i = 0; i < m; ++i) cin >> b[i];
int j = 0;
int cnt = 0;
for(int i = 0; i < n; ++i){
while(j < m and a[i] != b[j]) j++;
if(j < m and a[i] == b[j]){
cnt++;
j++;
}
}
cout << (cnt == n ? "Yes" : "No") << "\n";
}
再给一下优雅的实现方式(复制观摩y式)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> a(n), b(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;
while(i < n and j < m){
if(a[i] == b[j]) i++;
j++;
}
cout << (i == n ? "Yes" : "No") << "\n";
}