Acwing---2816. 判断子序列

1.题目

给定一个长度为 $n$ 的整数序列 $a1,a2,\dots ,an$ 以及一个长度为 $m$ 的整数序列 $b1,b2,\dots ,bm$。

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

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

输入格式
第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，表示 $a1,a2,\dots ,an$。

第三行包含 $m$ 个整数，表示 $b1,b2,\dots ,bm$。

输出格式
如果 $a$ 序列是 $b$ 序列的子序列，输出一行 $Yes$。

否则，输出 $No$。

数据范围
$1\le n\le m\le 105$,

$-109\le ai,bi\le 109$

$-109\le li\le ri\le 109$

输入样例：

3 5
1 3 5
1 2 3 4 5

输出样例：

Yes

2.基本思想

双指针

3.代码实现

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main{
   
    static int N = 100010;
    static int[] a = new int[N], b = new int[N];

    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
        for (int i = 1; i <= m; i++) b[i] = sc.nextInt();

        int j = 1;
        boolean flag = true;
        for (int i = 1; i <= n; i++) {
   
            while (j <= m && a[i] != b[j]) j++;
            if (j > m) {
   
                flag = false;
                break;
            }
            j++;
        }
        System.out.println(flag==true?"Yes":"No");
    }
}