Algorytmy i struktury danych · Senior · Pytanie 64 z 75
Jak znaleźć wszystkie pary o danej sumie w tablicy z duplikatami, nie licząc ich dwa razy?
- 1Sortować i szukać binarnie każdego elementu, dodając każde trafienie
- ✓Poprawna odpowiedź: Policzyć wartości w mapie i łączyć liczniki, obsługując x = target - x
- 3Włożyć wartości do
Seti przejść go raz
Wyjaśnienie
Dla każdego różnego x połącz go z count[target - x]; gdy x równa się dopełnieniu, użyj c × (c - 1) / 2. Przetwarzaj każdą parę wartości raz (x < dopełnienie). Set gubi liczniki.