一、题目来源 AcWing算法基础课-2816.判断子序列二、题目描述
给定一个长度为 \(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 51 3 51 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 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 > a[i]; for (int i = 0; i > b[i]; int i = 0; for (int j = 0; j < m; ++j) if (i < n && a[i] == b[j])//如果这里不加 i = n ++ i; if (i == n) puts("Yes"); else puts("No"); return 0;}