Algorytmy i struktury danych · Middle · Pytanie 19 z 75
Two Sum na posortowanej tablicy: jakie jest podejście O(n) bez dodatkowej pamięci?
- 1Wyszukiwanie binarne pary dla każdego elementu
- 2Włożenie wszystkich elementów do mapy przed szukaniem
- ✓Poprawna odpowiedź: Dwa wskaźniki z obu końców przesuwane według sumy
Wyjaśnienie
Posortowanie mówi, który wskaźnik przesunąć: zwiększenie lewej wartości podnosi sumę, zmniejszenie prawej ją obniża. Mapa też działa w O(n), ale potrzebuje O(n) pamięci.