Tenho 2 listas de números inteiros,

l1 = new ArrayList();
l2 = new ArrayList();

Quero descobrir itens duplicados em ambos, tenho a minha abordagem usual: -

for (Integer i : l1)
{
 if(l2.contains(i)){
    System.out.println("Found!");
  } 
}

Eu ouvicontains() éO(n), fazendo minha implementaçãoO(n^2).

Existe uma maneira melhor de fazer isso (menos deO(n^2))?