一、题目来源
二、题目描述
给定一个长度为 \(n\) 的整数序列 \(a_1,a_2,…,a_n\) 以及一个长度为 \(m\) 的整数序列 \(b_1,b_2,…,b_m\)。
请你判断 \(a\) 序列是否为 \(b\) 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {\(a_1,a_3,a_5\)} 是序列 {\(a_1,a_2,a_3,a_4,a_5\)} 的一个子序列。
输入格式
第一行包含两个整数 \(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\)
输入样例：
3 5
1 3 5
1 2 3 4 5
输出样例：
Yes
三、算法思路
本题比较简单，使用双指针解决问题。
思路如下：
-
\(i\) 指针从 \(a\) 数组开始枚举， \(j\) 指针从 \(b\) 数组开始枚举。
-
遇到 \(a[i] == b[j]\) 则 \(i\) 指针右移。
-
只要 \(a\) 数组和 \(b\) 数组都没有遍历完，那么一直遍历下去。
-
最后如果左指针 \(i == n\) ，则说明是子序列，如果没到 \(n\) ，则不是子序列。
- 两个数组都只会遍历一遍，所以时间复杂度为 \(O(m + n)\)。
- 为什么第三步要加一个判断，判断 \(a\) 数组有没有被遍历完呢？因为可能出现一下这种结果，\(a\) 数组是 \(1\) ， \(b\) 数组是 \(1\) \(0\)，已经匹配完了之后 \(i\) 指针还会继续往下走，如果后面的判断是 \(i == n\) ，那么就会出现问题。
- 也可以修改后面的判断为 \(i >= n\) ，这样也可以忽略前面的有没有遍历完的问题。
四、源代码
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[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 i = 0;
for (int j = 0; j < m; ++j)
if (i < n && a[i] == b[j]) //如果这里不加 i < n，则后面的判断条件应修改为 i >= n
++ i;
if (i == n) puts("Yes");
else puts("No");
return 0;
}