判断子序列（双指针）一图搞定

给定一个长度为 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,
−10^9≤ai,bi≤10^9

输入样例：

  

   

    

     

    
    

     

      3 5
     
    
   

    

     

    
    

     

      1 3 5
     
    
   

    

     

    
    

     

      1 2 3 4 5
     
    
  
 

输出样例：

Yes

 

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int N = 100010;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      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) puts("Yes");
     
    
   

    

     

    
    

     
    else puts("No");
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

直接两个数组两个指针分别匹配就可了。

（PS：由于CSDN每天只能发10篇，太限制小伙伴的想象了，大家可以访问我的cnblog:博客园）

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120596540