Two-Sum og de mange variantene
Løs two-sum, three-sum, four-sum og two-sum with sorted array med hash-kart og to pekere, og sammenlign tids- og plasskostnader.
Two-Sum og de mange variantene er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Two-sum: den klassiske intervjuoppgaven
LeetCode 1 «Two Sum»: Gitt et usortert array og en target skal De returnere indeksene til to elementer som summerer seg til target. Den brutale O(n²)-tilnærmingen kontrollerer alle par. Den optimale O(n)-tilnærmingen bruker en hash map: For hvert element x kontrollerer De om target - x allerede finnes i map-en. Hvis ja, returnerer De indeksene til paret. Hvis nei, lagrer De x og indeksen i map-en.
Two-sum er ofte den aller første oppgaven i et intervju — hvis De kan den grundig, signaliserer det at De er klar for vanskeligere oppgaver.
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]Hvorfor hash map fungerer for two-sum
Hash map-en lagrer hvert element som er sett så langt. Når elementet x behandles, danner x og target - x et gyldig par hvis target - x finnes i map-en. Det er avgjørende at komplementet kontrolleres før x lagres. Da unngår De at ett enkelt element pares med seg selv (for eksempel når x == target/2: Map-oppslaget skjer før x lagres, så det gir ikke treff med mindre det finnes to kopier).
# 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 i et sortert array (to pekere)
Hvis arrayet allerede er sortert og De trenger indeksene til verdiene (ikke de opprinnelige indeksene), kan De bruke teknikken med to pekere: en venstre- og en høyrepeker som starter i hver sin ende. Hvis summen er lik target, returnerer De resultatet. Hvis summen er for liten, flytter De venstre peker mot høyre. Hvis summen er for stor, flytter De høyre peker mot venstre. Dette gir O(n) tid og O(1) plass — bedre enn hash map-tilnærmingen når arrayet er sortert og minnet er begrenset.
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»: Finn alle unike tripletter som summerer seg til null. Sorter arrayet, lås ett element om gangen, og bruk to pekere på det gjenværende sorterte delarrayet. Hopp over dupliserte verdier for å unngå dupliserte tripletter. Tid: O(n²) — optimalt for dette problemet, siden selve resultatet kan inneholde O(n²) tripletter.
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»: Finn alle unike kvadrupler som summerer seg til target. Utvid three-sum: Lås to elementer med to nøstede løkker (og hopp over duplikater), og bruk deretter to pekere på det indre delarrayet. Tid: O(n³). For k-sum generelt gjentas rekursjonen k-2 ganger, før De bruker to pekere, noe som gir tidskompleksitet 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 nærmest target
En vanlig variant er å finne paret med en sum som ligger nærmest target (summen trenger ikke være nøyaktig lik target). Sorter arrayet og bruk to pekere. Hold oversikt over den nærmeste summen De har sett så langt, og oppdater den når De finner et par med mindre absolutt avstand fra target. Denne O(n log n)-tilnærmingen er enkel å bruke etter sorteringen.
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 med flere par (alle par)
For å finne alle par som summerer seg til target sorterer De arrayet og bruker to pekere, mens De samler alle parene. Når De har funnet et gyldig par, hopper De over duplikater fra begge ender før De fortsetter. Dette gir O(n log n) for sorteringen pluss O(n) for gjennomgangen — totalt O(n log n). Det er også mulig å bruke en hash map til å samle parene, men da må De håndtere duplikater nøye.
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)]Tell par med sum mindre enn K
En annen variant er å telle hvor mange par som har en sum mindre enn k. Sorter arrayet og bruk to pekere. Når nums[lo] + nums[hi] < k, er alle parene (lo, lo+1), (lo, lo+2), ..., (lo, hi) gyldige — det vil si hi - lo par. Flytt lo fremover. Ellers reduserer De hi. Total tid er O(n log n) for sorteringen pluss O(n) for opptellingen.
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 med hash map: håndtering av duplikater
Når den samme verdien kan forekomme flere ganger og De må telle gyldige par (ikke bare avgjøre om de finnes), lagrer De frekvenstellinger i map-en. For par der begge elementene er like, er antallet par fra en frekvens f lik f*(f-1)//2. For par der de to elementene er forskjellige, multipliserer De frekvensene deres. Slik kan De telle alle gyldige par på 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)...Gjenkjenne varianter av two-sum-mønsteret
Two-sum-mønsteret forekommer i mange forkledninger. Gjenkjenn det når en oppgave ber Dem finne to eller flere elementer som oppfyller en numerisk sammenheng (sum, produkt eller differanse). Kjernestrategien er alltid å låse ett element og deretter finne komplementet i en forhåndsberegnet struktur (hash map eller sortert array + peker). Utvid til k-sum ved å låse k-2 elementer med nøstede løkker og bruke grunntilfellet.
# 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')Kommunikasjon i intervjuet ved two-sum
Når two-sum dukker opp i et intervju, bør De forklare tankegangen høyt: «Jeg trenger to tall som summerer seg til target. For hvert tall x må jeg kontrollere om target-x finnes. Det kan jeg gjøre på O(1) med en hash map, noe som gir total tid på O(n) og plassbruk på O(n). Hvis arrayet derimot var sortert, kunne jeg brukt to pekere og O(1) plass.» Presenter begge tilnærmingene, og spør om det finnes begrensninger på plassbruken før De velger.
Hurtigsjekk
Test forståelsen Deres av konseptene innen Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: two-sum bruker et hash map til å kontrollere om komplementet finnes i O(1), noe som gir O(n) totalt, for sorterte tabeller oppnår to pekere O(1) plassbruk, og three-sum og four-sum reduseres til two-sum ved hjelp av sortering og nøstede løkker, med kjøretid på henholdsvis O(n²) og O(n³). Neste tema er mønstre for frekvenstelling og gruppering med defaultdict og Counter.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Two-Sum og de mange variantene» gratis?
Ja – hele teksten i «Two-Sum og de mange variantene» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Two-Sum og de mange variantene»?
Løs two-sum, three-sum, four-sum og two-sum with sorted array med hash-kart og to pekere, og sammenlign tids- og plasskostnader. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Two-Sum og de mange variantene»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Interne detaljer i hashfunksjoner og kollisjonshåndtering
- Two-Sum og de mange variantene
- Frekvenstelling og gruppering
- Lengste sammenhengende sekvens og LRU-cache