Algorytm wyznaczania części wspólnej dwóch list

Hej, mam za zadanie wyznaczyć części wspólne dwóch list (liczby, które są w obu listach).
Np. dla list1, które ma 9, 11, -3, 0 i list2 zawierającego 11, -3, 51, -15, odpowiedź to 11, -3.

Moja propozycja, taka ad hoc:

public static List<Integer> findCommonPart(List<Integer> numbers1, List<Integer> numbers2) {
    List<Integer> commonPart = new ArrayList<>();
    for (int i : numbers1) {
        for (int j : numbers2) {
            if (i == j)
                commonPart.add(i);
        }
    }

    return commonPart;
}

Tylko problem jest taki, że gdy jakaś liczba jest w pierwszej liście dwa razy, a w drugiej - raz (albo na odwrót), to dodaję ją do commonPart dwukrotnie (a powinno raz). Jeśli natomiast w obu listach jest po 2 razy - to tak samo powinno być w liście wynikowej. Jak to efektywnie usprawnić?

Przyjmuj Set<Integer> oraz zwracaj Set<Integer>; ewentualnie, jeśli chcesz/musisz zostać przy List, to problem rozwiążesz również wykorzystując hashset/btreeset w miejsce new ArrayList (btw, przy hashsecie Twoja funkcja stanie się O(n+m) zamiast O(n*m)).

Btw, ten common part nazywa się intersection :-)

@Patryk27 - przepraszam, ale niedokładnie się wyraziłem. Jak w obu listach liczba jest dwa razy - to w wynikowej też powinna być 2 razy. Natomiast jak w jednej jest 2 razy, a w drugiej - tylko 1 raz, no to w wynikowej powinna być raz.
Z tego co wiem - Set nie pozwala na duplikaty

Zrób sobie kopię "wewnętrznej" listy i usuwaj z niej wykorzystane elementy.
W wewnętrznym bloku if brakuje ci break.

Posortuj obie listy. Wtedy możesz sprawdzać część wspólną poprzez dwa kursory przesuwające się po obu listach

    final Map<Integer, Long> map1 = numbers1.stream().collect(Collectors.groupingBy(x -> x, Collectors.counting()));
    final Map<Integer, Long> map2 = numbers2.stream().collect(Collectors.groupingBy(x -> x, Collectors.counting()));

    return map1.entrySet().stream().map(entry -> {
        final Long val2 = map2.get(entry.getKey());
        return val2 != null ?
                Stream.generate(entry::getKey).limit(Math.min(val2, entry.getValue()))
                : Stream.empty();
    }).flatMap(x -> ((Stream<Integer>) x)).toList();

jeśli kolejność Cię nie interesuje to możesz to zrobić w ten sposób, jakieś O(3*n) w najgorszym razie tak na oko