当前位置: 代码迷 >> 综合 >> AcWing.2816.判断子序列
  详细解决方案

AcWing.2816.判断子序列

热度:117   发布时间:2023-11-21 18:53:50.0

题干:
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm

请你判断 a序列是否为 b序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5}是序列 {a1,a2,a3,a4,a5}的一个子序列。

输入格式

第一行包含两个整数 n,m

第二行包含 n个整数,表示 a1,a2,…,an

第三行包含 m个整数,表示 b1,b2,…,bm

输出格式

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

数据范围

1≤n≤m≤105

?109≤ai,bi≤109

输入样例:

3 5
1 3 5
1 2 3 4 5

输出样例:

Yes

解析:
已知利用双指针算法能找出在b中的和a相等的子序列,而反之却不一定会成立,所以假设在b数组内部有子序列和a相等,需要证明出来利用双指针算法能将其找出来。
在这里插入图片描述
假设存在一组匹配,验证双指针算法能否将其找出来;
假设在第一个数组的第一个点,在b数组内找到的恰好是匹配的那个点,但是到了第二个匹配的点后就不一样了,他匹配的是图示匹配点的前方的点,有双指针算法的特点,他找的是第一个在b数组内匹配的点,就算是找到的不同的匹配的点,那也一定是在前面的点,是不影响后面元素继续匹配的,所以以此类推,反之也是成立的由此证明双指针算法的可行性。
上述操作如下图所示:
在这里插入图片描述不同的是匹配了绿线,而并非是原先预定的红线匹配,但是由于双指针算法的特点,找的一定是第一个相匹配的点,若匹配一定是第一个匹配的位置,所以一定是在他的前面的,所以一定不会对后续的匹配造成影响。

代码实现:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;
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, j = 0;while(i < n && j < m ){
    if(a[i] == b[j]) i ++ ;j ++ ;//无论是否匹配成功,j指针均向后移动;}if(i == n) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}