【题目来源】
AcWing：2816. 判断子序列 - AcWing题库
【题目描述】
给定一个长度为 \(n\) 的整数序列 \(a_1,a_2,\dots,a_n\) 以及一个长度为 \(m\) 的整数序列 \(b_1,b_2,\dots,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,\dots,a_n\)。
第三行包含 \(m\) 个整数，表示 \(b_1,b_2,\dots,b_m\)。
【输出】
如果 \(a\) 序列是 \(b\) 序列的子序列，输出一行 Yes。
否则，输出 No。
【输入样例】
3 5
1 3 5
1 2 3 4 5
【输出样例】
Yes
【解题思路】
【算法标签】
《AcWing 2816 判断子序列》 #双指针#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 100010; // 定义数组最大长度int n, m; // n: 数组a的长度, m: 数组b的长度
int a[N], b[N]; // 两个待比较的数组int main()
{// 输入数组a的长度和数组b的长度scanf("%d%d", &n, &m);// 输入数组a的元素for (int i = 0; i < n; i++){scanf("%d", &a[i]);}// 输入数组b的元素for (int i = 0; i < m; i++){scanf("%d", &b[i]);}// 双指针初始化int i = 0, j = 0; // i指向数组a，j指向数组b// 遍历两个数组while (i < n && j < m){// 如果当前元素匹配，移动数组a的指针if (a[i] == b[j]){i++;}// 无论是否匹配，都要移动数组b的指针j++;}// 判断数组a是否是数组b的子序列if (i == n){puts("Yes"); // 数组a的所有元素都匹配到了}else{puts("No"); // 数组a还有元素未匹配}return 0;
}
【运行结果】
3 5
1 3 5
1 2 3 4 5
Yes