Java代码
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[] a = new int[n];//注意这里必须要是n,m 如果是N=100010的话,while循环会一直向前走
int[] b = new int[m];
for(int i = 0; i < n; i ++) a[i] = in.nextInt();
for(int i = 0; i < m; i ++) b[i] = in.nextInt();
int i = 0 , j = 0 ; //i指针在序列a走,j指针在序列b走
while(i < a.length && j < b.length){
if(b[j] == a[i]) i++; //如果匹配到了,i,j指针都向前走,否则只有j指针向前走
j++;
}
//当a数组匹配完最后一个数字5以后,i++,i就会到a.length的位置,而不是-1
if(i == a.length) System.out.print("Yes");
else System.out.print("No");
}
}
算法思想
1:声明两个指针i,j,i指针在序列a走,j指针在序列b走;
2:j指针循环长序列来不断的匹配a数组中的元素;匹配到了,i,j指针都向前走一步,匹配不到,j指针不断向右寻找
3:如果j指针把a数组中的元素全部都匹配完了,这时候i指针是指向a数组的最后的,那就可以说明a序列是b序列的子序列,否则不是