Dwa wskaźniki w posortowanej tablicy
Przesuwanie końców do środka w celu znalezienia celu
Dwa wskaźniki w posortowanej tablicy to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Dlaczego dwa wskaźniki
Technika dwóch wskaźników przegląda tablicę za pomocą dwóch indeksów zamiast zagnieżdżonych pętli, zamieniając wiele pomysłów o złożoności O(n^2) w jedno przejście O(n). 🎯
Posortowanie to klucz
Klasyczna wersja wymaga posortowanej tablicy. Kolejność pozwala wyciągać wnioski: przesunięcie w prawo zwiększa wartość, a w lewo ją zmniejsza, więc każdy krok jest rzeczywistą decyzją.
Dwa wskaźniki na końcach
Jeden wskaźnik należy ustawić na lewym końcu, a drugi na prawym. Wskaźniki są skierowane ku sobie i będą stopniowo zmniejszać dzielącą je odległość.
left = 0
right = len(a) - 1Przesuwanie końców do środka
W każdym kroku należy przesunąć dokładnie jeden wskaźnik do środka. Kolejność elementów tablicy wskazuje, którą stronę należy przesunąć, aby zbliżyć się do celu.
Warunek pętli
Pętlę należy wykonywać, dopóki zachodzi warunek left < right. Gdy wskaźniki się spotkają lub przetną, każda użyteczna para zostanie sprawdzona i można zakończyć działanie.
while left < right:
# inspect a[left] and a[right]
passOdczytywanie bieżącej sumy
Wyrażenie a[left] + a[right] należy traktować jako bieżącego kandydata. Porównanie go z wartością docelową wskazuje, czy następna wartość powinna być większa, czy mniejsza.
total = a[left] + a[right]Za mała suma: przesuń left
Jeśli suma jest mniejsza od wartości docelowej, potrzeba więcej. Należy przesunąć wskaźnik left w prawo, w stronę większych wartości, ponieważ tablica jest posortowana rosnąco.
if total < target:
left += 1Za duża suma: przesuń right
Jeśli suma jest większa od wartości docelowej, potrzeba mniej. Należy przesunąć wskaźnik right w lewo, w stronę mniejszych wartości, aby zmniejszyć sumę.
elif total > target:
right -= 1Każdy krok eliminuje część pracy
Każde przesunięcie eliminuje całą grupę par, których nie trzeba już sprawdzać. Dlatego przejście ma złożoność liniową, a nie kwadratową.
Dlaczego algorytm pozostaje poprawny
Odrzucane są wyłącznie pary, które nie mogą pasować, więc poprawna odpowiedź nigdy nie zostaje pominięta. To bezpieczeństwo sprawia, że metoda dwóch wskaźników jest godna zaufania w konkursach.
Nie tylko punkty końcowe
Ta sama idea zasila różne warianty: odwracanie elementów w miejscu, partycjonowanie i scalanie. Po opanowaniu wskaźników poruszających się ku sobie wszystkie te zastosowania stają się znajome.
Szybkie sprawdzenie
Przeszukują Państwo posortowaną tablicę od obu końców w poszukiwaniu sumy docelowej.
Podsumowanie
Dwa wskaźniki przechodzą przez posortowaną tablicę od obu końców, przesuwając jeden z nich do środka w każdym kroku, dopóki zachodzi left < right. Liniowo, poprawnie i jako podstawa wielu sztuczek. 🚀
Często zadawane pytania
Czy lekcja „Dwa wskaźniki w posortowanej tablicy” jest bezpłatna?
Tak — pełny tekst „Dwa wskaźniki w posortowanej tablicy” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Dwa wskaźniki w posortowanej tablicy”?
Przesuwanie końców do środka w celu znalezienia celu Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Dwa wskaźniki w posortowanej tablicy”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Dwa wskaźniki w posortowanej tablicy
- Znajdowanie pary o zadanej sumie
- Usuwanie duplikatów w miejscu
- Scalanie dwóch posortowanych sekwencji