Algorytmy i struktury danych · Junior · Pytanie 62 z 75
Two Sum: znajdź dwie liczby w nieposortowanej tablicy, które sumują się do target. Jakie jest podejście O(n)?
- 1Posortować tablicę i zwrócić dwa najmniejsze elementy
- 2Sprawdzić każdą możliwą parę dwiema zagnieżdżonymi pętlami
- ✓Poprawna odpowiedź: Sprawdzać, czy
target - xjest w mapie już widzianych liczb
Wyjaśnienie
Jedno przejście: jeśli target - x już się pojawiło, para jest znaleziona; w przeciwnym razie zapamiętaj x i jego indeks. Sprawdzanie wszystkich par to O(n²). Sortowanie daje O(n log n) i gubi oryginalne indeksy.