Two-Sum i jego liczne warianty
Rozwiążą Państwo zadania two-sum, three-sum, four-sum i two-sum with sorted array za pomocą map haszujących i dwóch wskaźników, porównując koszty czasowe i pamięciowe.
Two-Sum i jego liczne warianty to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 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.
Two-Sum: klasyczny problem rekrutacyjny
LeetCode 1 „Two Sum”: dla nieposortowanej tablicy i wartości docelowej należy zwrócić indeksy dwóch elementów, których suma jest równa wartości docelowej. Siłowe podejście O(n²) sprawdza wszystkie pary. Optymalne podejście O(n) wykorzystuje mapę haszującą: dla każdego elementu x należy sprawdzić, czy target - x już istnieje w mapie. Jeśli tak, należy zwrócić parę indeksów. W przeciwnym razie należy zapisać x i jego indeks w mapie.
Two-sum jest często pierwszym zadaniem podczas rozmowy rekrutacyjnej — jego bardzo dobra znajomość sygnalizuje gotowość do rozwiązywania trudniejszych problemów.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Dlaczego mapa haszująca działa w Two-Sum
Mapa haszująca przechowuje każdy dotychczas napotkany element. Podczas przetwarzania elementu x, jeśli target - x znajduje się w mapie, te dwa elementy tworzą poprawną parę. Kluczowe jest sprawdzenie dopełnienia przed zapisaniem x, co zapobiega sytuacji, w której pojedynczy element zostałby sparowany z samym sobą (np. gdy x == target/2, sprawdzenie mapy odbywa się przed zapisaniem x, więc nie dopasuje się, chyba że istnieją dwie kopie).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iTwo-Sum w posortowanej tablicy (dwa wskaźniki)
Jeśli tablica jest już posortowana i potrzebne są indeksy wartości (a nie ich oryginalne indeksy), należy użyć techniki dwóch wskaźników: wskaźniki left i right rozpoczynają działanie na przeciwległych końcach tablicy. Jeśli suma jest równa target, należy zwrócić wynik. Jeśli suma jest za mała, należy przesunąć left w prawo. Jeśli suma jest za duża, należy przesunąć right w lewo. Złożoność czasowa wynosi O(n), a pamięciowa O(1) — to lepsze rozwiązanie niż mapa haszująca, gdy tablica jest posortowana, a pamięć jest ograniczona.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Three-Sum (LeetCode 15)
LeetCode 15 „Three Sum”: należy znaleźć wszystkie unikalne trójki, których suma wynosi zero. Należy posortować tablicę, ustalać po kolei jeden element i zastosować technikę dwóch wskaźników do pozostałego posortowanego podciągu. Wartości powtarzające się należy pomijać, aby uniknąć zduplikowanych trójek. Złożoność czasowa: O(n²) — jest to optymalne dla tego problemu, ponieważ sam wynik może zawierać O(n²) trójek.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Four-Sum (LeetCode 18)
LeetCode 18 „Four Sum”: należy znaleźć wszystkie unikalne czwórki, których suma wynosi target. Podejście rozszerza Three-Sum: należy ustalić dwa elementy za pomocą dwóch zagnieżdżonych pętli (pomijając duplikaty), a następnie zastosować technikę dwóch wskaźników do wewnętrznego podciągu. Złożoność czasowa: O(n³). Ogólnie w problemie k-sum schemat polega na rekurencyjnym wykonaniu kroku k-2 razy, a następnie zastosowaniu dwóch wskaźników, co daje złożoność O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Two-Sum: suma najbliższa wartości docelowej
Częsty wariant polega na znalezieniu pary o sumie najbliższej wartości docelowej (suma nie musi być z nią dokładnie równa). Należy posortować tablicę i użyć dwóch wskaźników. Trzeba śledzić najbliższą dotychczas znalezioną sumę i aktualizować ją za każdym razem, gdy para ma mniejszą bezwzględną różnicę względem wartości docelowej. To proste podejście ma złożoność O(n log n) po sortowaniu.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Two-Sum z wieloma parami (wszystkie pary)
Aby znaleźć wszystkie pary, których suma jest równa wartości docelowej, należy posortować tablicę i użyć dwóch wskaźników, zbierając wszystkie pary. Po znalezieniu poprawnej pary należy pominąć duplikaty z obu końców przed kontynuowaniem. Daje to O(n log n) za sortowanie oraz O(n) za skanowanie, czyli łącznie O(n log n). Zbieranie par za pomocą mapy haszującej również jest poprawne, ale wymaga ostrożnego postępowania z duplikatami.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Zliczanie par o sumie mniejszej niż K
Inny wariant polega na zliczeniu par, których suma jest mniejsza niż k. Należy posortować tablicę i użyć dwóch wskaźników. Gdy nums[lo] + nums[hi] < k, wszystkie pary (lo, lo+1), (lo, lo+2), ..., (lo, hi) są poprawne — jest ich hi - lo. Należy zwiększyć lo. W przeciwnym razie należy zmniejszyć hi. Łączna złożoność czasowa wynosi O(n log n) za sortowanie oraz O(n) za zliczanie.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyTwo-Sum z mapą haszującą: obsługa duplikatów
Gdy ta sama wartość może wystąpić wiele razy i trzeba policzyć liczbę poprawnych par (a nie tylko sprawdzić ich istnienie), należy przechowywać w mapie częstości występowania. Dla par, których oba elementy są równe, liczba par dla częstości f wynosi f*(f-1)//2. Gdy elementy pary różnią się, należy pomnożyć ich częstości. Pozwala to zliczyć wszystkie poprawne pary w czasie O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Rozpoznawanie wariantów wzorca Two-Sum
Wzorzec two-sum występuje w wielu postaciach. Należy go rozpoznać, gdy zadanie wymaga znalezienia co najmniej dwóch elementów spełniających zależność liczbową (sumę, iloczyn lub różnicę). Podstawowa strategia zawsze wygląda tak samo: ustalić jeden element, a następnie znaleźć jego dopełnienie w uprzednio przygotowanej strukturze (mapie haszującej albo posortowanej tablicy i wskaźniku). Podejście można rozszerzyć do k-sum, ustalając k-2 elementów za pomocą zagnieżdżonych pętli i stosując przypadek bazowy.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Komunikacja podczas rozmowy rekrutacyjnej dotycząca Two-Sum
Gdy podczas rozmowy rekrutacyjnej pojawi się problem two-sum, należy głośno prześledzić tok rozumowania: „Potrzebuję dwóch liczb, których suma jest równa target. Dla każdej liczby x muszę sprawdzić, czy target-x istnieje. Mogę odpowiedzieć na to pytanie w O(1) za pomocą mapy haszującej, uzyskując łączną złożoność czasową O(n) i pamięciową O(n). Jeśli tablica byłaby posortowana, alternatywnie mógłbym użyć dwóch wskaźników i pamięci O(1)”. Należy przedstawić oba podejścia i przed dokonaniem wyboru zapytać o ograniczenia dotyczące pamięci.
Szybki test
Proszę sprawdzić znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: algorytm two-sum korzysta z mapy haszującej do sprawdzania, czy istnieje dopełnienie w O(1), co daje O(n) dla całego rozwiązania, dla posortowanych tablic dwa wskaźniki zapewniają użycie pamięci O(1), a three-sum i four-sum sprowadzają się do two-sum dzięki sortowaniu i zagnieżdżonym pętlom, działając odpowiednio w O(n²) i O(n³). Następnie omówimy schematy zliczania częstotliwości oraz grupowanie z użyciem defaultdict i Counter.
Często zadawane pytania
Czy lekcja „Two-Sum i jego liczne warianty” jest bezpłatna?
Tak — pełny tekst „Two-Sum i jego liczne warianty” 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 „Two-Sum i jego liczne warianty”?
Rozwiążą Państwo zadania two-sum, three-sum, four-sum i two-sum with sorted array za pomocą map haszujących i dwóch wskaźników, porównując koszty czasowe i pamięciowe. Ć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 2 z 4.
Ile czasu zajmuje lekcja „Two-Sum i jego liczne warianty”?
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
- Wewnętrzne działanie funkcji haszującej i obsługa kolizji
- Two-Sum i jego liczne warianty
- Zliczanie częstotliwości i grupowanie
- Najdłuższy spójny ciąg i pamięć podręczna LRU