题目描述

题目大意&链接

给定 a，b 两个子序列，判断 a 序列是否是 b 序列的子序列，是：Yes，否：No。

输入输出样例：
输入：

3 5
1 3 5
1 2 3 4 5

输出：

Yes

详情：ac_2816判断子序列

解题思路

这题采用双指针的思想，可以参考ac_800数组元素的目标和：

定义 i，j 指针分别指向 a，b 序列的左端点，j一直右移循环遍历，若 a[i] == b[j] 则 i++ ，当 i==n 时则 a 是 b 的子序列：
int i = 0, j = 0;
while(i < n && j < m)
{
if(a[i] == b[j]) i++;
j++;
}

完整代码

#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < m; i++) scanf("%d", &b[i]);
    
    int i = 0, j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j]) i++;
        j++;
    }
    
    if(i == n) printf("Yes");
    else printf("No");
    return 0;
}

时间和空间复杂度

时间复杂度：O(n + m)
空间复杂度：O(n + m)