17.Acwing基础课第2816题-简单-判断子序列

17.Acwing基础课第2816题-简单-判断子序列

题目描述

给定一个长度为 \(n\) 的整数序列 \(a_1,a_2,…,a_n\)以及一个长度为 m 的整数序列 \(b_1,b_2,…,b_m\)。
请你判断 \(a\) 序列是否为 \(b\) 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 \({a1,a3,a5}\)是序列 \({a1,a2,a3,a4,a5}\)的一个子序列。
输入格式

第一行包含两个整数 \(n,m\)。
第二行包含\(n\)个整数，表示\(a_1,a_2,…,a_n\)。
第三行包含 \(m\)个整数，表示\(b_1,b_2,…,b_m\)。
输出格式

如果 \(a\) 序列是 \(b\) 序列的子序列，输出一行 Yes。
否则，输出 No。
数据范围

\(1≤n≤m≤10^5,\)
\(−10^9≤a_i,b_i≤10^9\)
输入样例

1. 3 5
2. 1 3 5
3. 1 2 3 4 5

复制代码

输出样例

1. Yes

复制代码

思路解析：

算法：双指针

代码：

1. #include <iostream>
2. #include <cstring>
4. using namespace std;
6. const int N = 100010;
8. int n, m;
9. int a[N], b[N];
11. int main()
12. {
13.     scanf("%d%d", &n, &m);
14.     for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
15.     for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);
17.     int i = 0, j = 0;
18.     while (i < n && j < m)
19.     {
20.         if (a[i] == b[j]) i ++ ;
21.         j ++ ;
22.     }
24.     if (i == n) puts("Yes");
25.     else puts("No");
27.     return 0;
28. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！