Dwa wskaźniki: przeciwległe końce
Wykorzystają Państwo lewe i prawe wskaźniki przesuwające się ku sobie, aby rozwiązywać problemy sumy par w posortowanych tablicach, poprawnego palindromu i gromadzenia wody deszczowej.
Dwa wskaźniki: przeciwległe końce to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 3 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Idea dwóch wskaźników
Technika dwóch wskaźników wykorzystuje dwie zmienne indeksujące, które przesuwają się ku sobie (lub w tym samym kierunku), aby ograniczyć potrzebę stosowania zagnieżdżonych pętli. Zamiast sprawdzać każdą parę w O(n²), przy każdym porównaniu wykonuje się postęp, dzięki czemu algorytm kończy działanie w O(n). Prawie zawsze wymaga to wcześniejszego posortowania tablicy, ponieważ sortowanie pozwala określić kierunek przesunięcia każdego wskaźnika na podstawie tego, czy suma bieżącej pary jest zbyt duża, czy zbyt mała.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Two Sum w posortowanej tablicy
W posortowanej tablicy należy umieścić jeden wskaźnik na lewym końcu (najmniejszy element), a drugi na prawym końcu (największy element). Jeśli suma jest zbyt mała, należy przesunąć lewy wskaźnik w prawo, aby ją zwiększyć. Jeśli suma jest zbyt duża, należy przesunąć prawy wskaźnik w lewo, aby ją zmniejszyć. Każda iteracja przesuwa co najmniej jeden wskaźnik, więc pętla wykonuje najwyżej n iteracji: łącznie O(n) po sortowaniu. Co ważne, każde przesunięcie jest formalnie uzasadnione dzięki uporządkowaniu elementów.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Sprawdzanie, czy ciąg jest palindromem
Łańcuch znaków jest palindromem, jeśli czytany od przodu i od tyłu brzmi tak samo. Należy użyć dwóch wskaźników zaczynających się na obu końcach i przesuwających się do środka: porównywać znaki, pomijać znaki niealfanumeryczne i zatrzymać się, gdy wskaźniki się miną. Działanie zajmuje O(n) czasu i O(1) dodatkowej pamięci — jest znacznie prostsze niż odwrócenie łańcucha i porównanie go, które wymaga przydzielenia O(n) dodatkowej pamięci.
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseThree Sum: sortowanie + dwa wskaźniki
Problem Three Sum polega na znalezieniu wszystkich unikatowych trójek, których suma wynosi zero. Należy posortować tablicę, następnie ustalić każdy element nums[i] i przeprowadzić wyszukiwanie za pomocą dwóch wskaźników w pozostałej podtablicy, szukając pary o sumie -nums[i]. Należy pomijać duplikaty zarówno ustalonego elementu, jak i znalezionej pary, aby uniknąć powtarzających się trójek. Łączny czas: O(n²) po sortowaniu w O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Pojemnik z największą ilością wody
Mając wysokości pionowych linii, należy znaleźć dwie linie tworzące pojemnik mieszczący najwięcej wody. Pole = min(height[left], height[right]) × (right - left). Zachłannie należy przesuwać do środka wskaźnik znajdujący się przy krótszej linii: przesunięcie wskaźnika przy wyższej linii może tylko zmniejszyć szerokość bez zwiększenia ograniczenia wysokości. Ta zachłanna decyzja jest optymalna i daje czas O(n).
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Podnoszenie elementów posortowanej tablicy do kwadratu
Należy podnieść każdy element posortowanej tablicy (która może zawierać liczby ujemne) do kwadratu i zwrócić wynik w posortowanej kolejności. Kwadraty liczb ujemnych są duże, a kwadraty liczb dodatnich są najmniejsze w środku. Należy umieścić dwa wskaźniki na obu końcach i wypełniać tablicę wynikową od prawej do lewej (od największych do najmniejszych wartości). Czas O(n) i O(n) pamięci na wynik — znacznie lepiej niż podnoszenie do kwadratu, a następnie sortowanie w O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Zatrzymywanie wody deszczowej
Objętość wody zatrzymanej na indeksie i jest równa min(max_left, max_right) - height[i]. Podejście z dwoma wskaźnikami polega na utrzymywaniu bieżących wartości max_left i max_right. Gdy max_left < max_right, lewa strona jest wąskim gardłem — należy obsłużyć lewy wskaźnik. W przeciwnym razie należy obsłużyć prawy. Eliminuje to konieczność używania oddzielnych tablic maksymalnych wartości z lewej i prawej strony, zapewniając O(1) dodatkowej pamięci.
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Dlaczego zachłanne przesuwanie wskaźnika działa
Częste pytanie uzupełniające podczas rozmowy rekrutacyjnej brzmi: dlaczego można bezpiecznie odrzucić mniejszy wskaźnik? Szkic dowodu dla problemu pojemnika z największą ilością wody: załóżmy, że height[left] < height[right]. Każda para (left, j) dla j < right daje pole ≤ height[left] × (j-left) < height[left] × (right-left) ≤ bieżące pole. Zatem żadna para zaczynająca się od 'left' i mająca prawy indeks mniejszy niż 'right' nie może dać większego pola niż bieżące. Można je bezpiecznie pominąć, przesuwając left.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Para o najmniejszej różnicy w posortowanej tablicy
Należy znaleźć parę liczb w posortowanej tablicy, której różnica bezwzględna jest najmniejsza. Należy użyć dwóch wskaźników sąsiednich elementów (a nie wskaźników ustawionych na przeciwległych końcach), przesuwając je wspólnie i obliczając |nums[i] - nums[i+1]| dla każdej kolejnej pary. W posortowanej tablicy najmniejsza różnica zawsze występuje między sąsiednimi elementami, ponieważ sortowanie umieszcza zbliżone wartości obok siebie. Po sortowaniu rozwiązanie działa w czasie O(n).
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Szablon dwóch wskaźników poruszających się od przeciwnych końców
Większość problemów z dwoma wskaźnikami poruszającymi się od przeciwnych końców opiera się na tym samym schemacie. Opanowanie tego szablonu pozwala szybko dostosować go do różnych zadań, także pod presją czasu. Najważniejsze decyzje to: (1) jaki warunek powoduje przesunięcie lewego wskaźnika, (2) jaki warunek powoduje przesunięcie prawego wskaźnika, (3) co stanowi rozwiązanie oraz (4) jak obsługiwać duplikaty. Przed napisaniem kodu należy ćwiczyć wyprowadzanie tych decyzji z treści problemu.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultZliczanie poprawnych par za pomocą dwóch wskaźników
Dwa wskaźniki umożliwiają również wydajne zliczanie par. W problemie „zlicz pary, których suma jest mniejsza niż target” dla posortowanej tablicy należy ustalić lewy wskaźnik i użyć prawego wskaźnika do znalezienia najbardziej prawego poprawnego indeksu prawego elementu. Wszystkie pary (left, left+1 to right) są poprawne — do licznika należy dodać right - left, a następnie przesunąć lewy wskaźnik. W ten sposób wszystkie poprawne pary są zliczane w czasie O(n), zamiast O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Szybki sprawdzian
Sprawdź swoją wiedzę na temat zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznano: dwa wskaźniki poruszające się od przeciwnych końców zastępują wyliczanie par w czasie O(n²) zbieżnością lewego i prawego wskaźnika w czasie O(n) dla posortowanych tablic, decyzja o tym, który wskaźnik przesunąć, wynika z własności monotonicznej problemu — należy przesunąć tę stronę, która w danym momencie ogranicza postęp oraz problemy three-sum, container-with-most-water, trapping rain water i weryfikacja palindromu sprowadzają się do tego samego podstawowego szablonu. Następnie omówione zostaną wzorce dwóch wskaźników: wolnego i szybkiego.
Często zadawane pytania
Czy lekcja „Dwa wskaźniki: przeciwległe końce” jest bezpłatna?
Tak — pełny tekst „Dwa wskaźniki: przeciwległe końce” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Dwa wskaźniki: przeciwległe końce”?
Wykorzystają Państwo lewe i prawe wskaźniki przesuwające się ku sobie, aby rozwiązywać problemy sumy par w posortowanych tablicach, poprawnego palindromu i gromadzenia wody deszczowej. Ćwiczysz DSA 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA 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 3 z 4.
Ile czasu zajmuje lekcja „Dwa wskaźniki: przeciwległe końce”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA 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
- Podstawy tablic i operacje w miejscu
- Sumy prefiksowe i sumy narastające
- Dwa wskaźniki: przeciwległe końce
- Dwa wskaźniki: wolny i szybki