解题思路
判断a数组是否是b数组的子序列,可以利用双指针,一个指向a数组开头,一个指向b数组开头,如果a[i]==b[i]
,说明a[i]是b数组的一员,则需要i++
判断a的下一个元素;否则j++
继续遍历b数组。遍历结束后,如果i指向a数组末尾的后一位,即i==n
,说明a数组被完全遍历,a数组的每一个元素都在b中按照次序出现过,所以a是b数组的子序列。如果i!=n
,说明a数组中有b数组不存在的元素,则a不是b的子序列。
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long[] a = new long[n];
long[] b = new long[m];
for (int i = 0; i < n; i ++) {
a[i] = sc.nextLong();
}
for (int j = 0; j < m; j ++) {
b[j] = sc.nextLong();
}
// 定义双指针,一个指向a数组开头,一个指向b数组开头
int i = 0, j = 0;
while (i < n && j < m) {
// 如果ai=bj,则说明ai是b数组的一员,则i++比较下一个元素;否则继续向后遍历b数组
if (a[i] == b[j]) i ++;
j++;
}
// 遍历结束后,如果i指针已经指向a数组末尾的后一位,说明a数组被完全匹配,则a是b的子序列
if (i == n) System.out.println("Yes");
// 否则说明a数组中有b数组不存在的值,a不是b的子序列
else System.out.println("No");
sc.close();
}
}