判断子序列

【题目描述】

AcWing 2816. 判断子序列

写法一

【思路】
枚举每一个a[i],查看b序列中是否有与之匹配的。若没有则j++，直至找到或者j出界。
若有匹配的则记录已经匹配的个数，同时i、j指针向前 。

伪代码

int len  = 0;
for( a[i])
    for(b[j])
    while( j < m - 1 && b[j] != a[i] ) j ++;
    //j指针向后移动
    if( a[i] == b[j]){
        len ++;
        j = j + 1;
    }
if( len == n) System.out.println("Yes");
else  System.out.println("No");

import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int a[] = new int[N];
    static int b[] = new int[N];
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt(), m = reader.nextInt();
        for(int i = 0; i < n; i ++) a[i] = reader.nextInt();
        for(int i = 0; i < m; i ++) b[i] = reader.nextInt();

        int len = 0;
        for(int i = 0, j = 0; i < n; i++)
        {
            while( j < m - 1 && a[i] != b[j]) j ++;
            if(a[i] == b[j]) {
                j = j + 1;
                len ++;
            }
        }
        if( len == n) System.out.println("Yes");
        else  System.out.println("No");
    }
}

写法二

看到一个更简便的解法： z林深时见鹿 题解
思路是：i、j分别指向b、a序列，j指针只有a[j]和b[i]匹配上才移动，而i一直往前移动直至最后遍历完。这样如果b是a的子序列那么j最后一定会为n。

import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int a[] = new int[N];
    static int b[] = new int[N];
    public static void main(String args[]){
        Scanner reader = new Scanner(System.in);
        int n = reader.nextInt(), m = reader.nextInt();
        for(int i = 0; i < n; i ++) a[i] = reader.nextInt();
        for(int i = 0; i < m; i ++) b[i] = reader.nextInt();

        int j = 0;
        for(int i = 0; i < m; i ++)
        {
            if( j < n && b[i] == a[j]) j ++;
        }
        if( j == n) System.out.println("Yes");
        else  System.out.println("No");
    }
}