java - 无法使此Java代码运行得更快

我正在参加一个在线裁判页面，在此页面上我解决了一个问题，但是我无法及时运行我的程序。代码如下:

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Set l = new HashSet();
String line;
String[] numStr;
 while(true){
  line = in.readLine();
  numStr = line.split("\\s");
  int a = Integer.parseInt(numStr[0]);
  if(a == 0){
     System.exit(0);
  }
  int n = 0;
  int b = Integer.parseInt(numStr[1]);
  l.clear();
  for(int i=0;i<a;i++){
    l.add(in.readLine());
  }
  for(int i=0;i<b;i++){
    if(l.contains(in.readLine())){
      n++;
    }
  }
  System.out.println(n);

我到达了一个测试点，对于一个200万项的测试用例(numStr =“1000000 1000000”)，它可以在1.5秒内运行，但是显然这对于​​测试用例是不够的(它说3000毫秒)。现在，我不知道如何使它更快，任何帮助将不胜感激!

问题:http://coj.uci.cu/24h/problem.xhtml?abb=1438

最佳答案

输入规范的“按升序”部分是关键:由于两个列表都是预先排序的，因此您可以将第一个列表读入数组，然后使用从最后一项位置到末尾的二进制搜索。数组来确定您是否有匹配项。实际上，即使线性搜索第一个数组也可能有效，因为您最多需要遍历一次。