题解 | #排队合影#

一开始想偏了，一眼看上去以为是求最大公共子序列 提交后发现不对，因为本题目只允许向左而不是左右均可移动。 我用 O(n2) 的时间复杂度暴力过了。 优化了一下第二重循环的时间。 等一个大佬的on解

import java.util.Scanner; import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in);

    // 注意 hasNext 和 hasNextLine 的区别\
    int n = sc.nextInt();
    sc.nextLine();
    int[] a = new int[n];
    int[] b = new int[n];
    for (int i = 0 ; i < n ; i++){
        a[i]= sc.nextInt();
    }
    sc.nextLine();
    for (int i = 0 ; i < n ; i++){
        b[i]= sc.nextInt();
    }
    int ans = 0;
    sc.nextLine();
    boolean []v = new boolean[n+1];
    Arrays.fill(v,false);
    int k  = 0 ;
    for (int i = 0 ; i< n ; i++){
      if (v[a[i]]==true ) continue;
        v[a[i]]=true;
        for (int j = k ; j< n ; j++){
            if (b[j]==a[i]) 
            {k = j+1 ; break;}
            if  (v[b[j]]==false )
            {
                ans++;
                v[b[j]] = true ;
                
            }
        }
    }
    System.out.println(ans)；
}

}