Проверить, похожи ли 2 массива, без хэширования или сортировки

Нам нужно проверить, похожи ли 2 массива или нет. Элементы также могут дублироваться. Например, A = {2,3,4,5,6,6} и B = {3,6,2,4,6,5} подобны.

У меня есть наивное решение:

foreach i:int in arr1
 foreach j:int in arr2
  {
    if(i == j)
     j = -1;
  } 

Теперь, если все элементы j равны -1, то мы можем сказать, что эти 2 массива похожи. Может ли кто-нибудь дать тестовый пример, в котором это не сработает (хотя я надеюсь, что сработает!)?

Также это O(n^2). Можем ли мы сделать лучше? Сортировка и хеширование не допускаются.