双指针——判断子序列

题目描述

给定一个长度为 n 的整数序列 a1, a2, …, an 以及一个长度为 m 的整数序列 b1, b2, ⋯, bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1, a3, a5} 是序列 {a1, a2, a3, a4, a5} 的一个子序列。

输入格式

第一行包含两个整数 n, m (1≤n≤m≤10^5)。
第二行包含 n 个整数，表示 a1, a2, …, an (−10^9≤ai≤10^9)。
第三行包含 m 个整数，表示 b1, b2, ⋯, bm (−10^9≤bi≤10^9)。

输出格式

如果 a 序列是 b 序列的子序列，输出一行 Yes。
否则，输出 No。

输入样例1

3 5
1 3 5
1 2 3 4 5

输出样例1

Yes

输入样例2

10 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 2 1

输出样例2 

No

输入样例3

3 10
1 1 2
1 1 1 1 1 1 1 1 1 1

输出样例3 

No

注释版代码

#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];
int main()
{
	int n,m,res=0;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int j=0;j<m;j++) scanf("%d",&b[j]);
	int i=0,j=0;
	while(i<n&&j<m)
	{
		if(a[i]==b[j])
		{
			i++;//因为n<m，所以i只能在匹配上的时候才能往后匹配
		}
		j++;//j往后走是为了能匹配上i
	}
	if(i==n)//如果最后匹配上的个数等于n，那就是说a这个数组都被匹配上了
	{
		printf("Yes\n");
	}
	else printf("No\n");
	return 0;
}