头条超市

判断子序列（双指针）

2023-11-22 09:04 由 grave-master 发表于 #其他

一、题目来源

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 5
1 3 5
1 2 3 4 5

输出样例：

Yes

三、算法思路

本题比较简单，使用双指针解决问题。

思路如下：

  1. \(i\) 指针从 \(a\) 数组开始枚举， \(j\) 指针从 \(b\) 数组开始枚举。

  2. 遇到 \(a[i] == b[j]\) 则 \(i\) 指针右移。

  3. 只要 \(a\) 数组和 \(b\) 数组都没有遍历完，那么一直遍历下去。

  4. 最后如果左指针 \(i == n\) ，则说明是子序列，如果没到 \(n\) ，则不是子序列。

  • 两个数组都只会遍历一遍，所以时间复杂度为 \(O(m + n)\)。
  • 为什么第三步要加一个判断，判断 \(a\) 数组有没有被遍历完呢？因为可能出现一下这种结果，\(a\) 数组是 \(1\) ， \(b\) 数组是 \(1\) \(0\)，已经匹配完了之后 \(i\) 指针还会继续往下走，如果后面的判断是 \(i == n\) ，那么就会出现问题。
  • 也可以修改后面的判断为 \(i >= n\) ，这样也可以忽略前面的有没有遍历完的问题。

四、源代码

#include <iostream>

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 < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    
    int i = 0;
    for (int j = 0; j < m; ++j)
        if (i < n && a[i] == b[j])		//如果这里不加 i < n，则后面的判断条件应修改为 i >= n
            ++ i;
            
    if (i == n) puts("Yes");
    else    puts("No");
    
    return 0;
}

热门相关：国破山河在   都市捉妖人   都市剑说   试婚100天：夜少，轻轻宠   龙骑战机