Two-sum och dess många varianter
Lös two-sum, three-sum, four-sum och two-sum with sorted array med hash maps och två pekare och jämför tids- och utrymmeskostnader.
Two-sum och dess många varianter är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 2 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Two-Sum: Det klassiska intervjuproblemet
LeetCode 1 'Two Sum': givet en osorterad array och ett målvärde ska ni returnera indexen för två element vars summa är målvärdet. Den brute-force-baserade O(n²)-metoden kontrollerar alla par. Den optimala O(n)-metoden använder en hash map: för varje element x kontrollerar ni om target - x redan finns i map:en. Om ja, returnerar ni indexparet. Om nej, lagrar ni x och dess index i map:en.
Two-sum är ofta det allra första problemet i en intervju — att kunna det utan och innan visar att ni är redo att gå vidare till svårare problem.
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]Varför hash map fungerar för Two-Sum
Hash map:en lagrar alla element som har setts hittills. När elementet x behandlas bildar de två elementen ett giltigt par om target - x finns i map:en. Det är avgörande att komplementet alltid kontrolleras innan x lagras. Därmed undviks fallet där ett enda element paras ihop med sig självt (om exempelvis x == target/2 görs map-kontrollen innan x lagras, så blir det ingen träff om det inte finns två kopior).
# 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 en sorterad array (två pekare)
Om arrayen redan är sorterad och ni behöver indexen för värdena (inte de ursprungliga indexen) använder ni tekniken med två pekare: en left-pekare och en right-pekare som börjar i varsin ände. Om summan är lika med target returnerar ni. Om summan är för liten flyttar ni left åt höger. Om summan är för stor flyttar ni right åt vänster. Detta tar O(n) tid och O(1) utrymme — bättre än hash map-metoden när arrayen är sorterad och minnet är begränsat.
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': hitta alla unika tripletter vars summa är noll. Sortera arrayen, fixera ett element i taget och använd tvåpekarmetoden på den återstående sorterade delarrayen. Hoppa över dubblettvärden för att undvika duplicerade tripletter. Tidskomplexitet: O(n²) — optimalt för det här problemet, eftersom själva resultatet kan innehålla 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': hitta alla unika fyrtupler vars summa är target. Utvidga three-sum: fixera två element med två nästlade loopar (hoppa över dubbletter) och använd sedan två pekare på den inre delarrayen. Tidskomplexitet: O(n³). För k-sum i allmänhet rekurrerar ni k-2 gånger och använder sedan två pekare, vilket ger tidskomplexiteten 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ärmast målet
En vanlig variant är att hitta paret med en summa som ligger närmast målet (summan behöver inte vara exakt lika med målet). Sortera arrayen och använd två pekare. Håll reda på den närmaste summan hittills och uppdatera den när ni hittar ett par med en mindre absolut avvikelse från målet. Den här metoden med tidskomplexiteten O(n log n) är enkel när arrayen väl har sorterats.
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 flera par (alla par)
Om ni vill hitta alla par vars summa är target sorterar ni arrayen och använder två pekare för att samla in alla par. När ni har hittat ett giltigt par hoppar ni över dubbletter från båda håll innan ni fortsätter. Det ger O(n log n) för sorteringen plus O(n) för genomsökningen — totalt O(n log n). Det går också att använda en hash map för att samla par, men då måste ni hantera dubbletter noggrant.
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)]Räkna par med en summa mindre än K
En annan variant är att räkna hur många par som har en summa mindre än k. Sortera arrayen och använd två pekare. När nums[lo] + nums[hi] < k gäller är alla par (lo, lo+1), (lo, lo+2), ..., (lo, hi) giltiga — det vill säga hi - lo par. Flytta fram lo. Annars minskar ni hi. Den totala tidskomplexiteten är O(n log n) för sorteringen plus O(n) för räkningen.
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: Hantera dubbletter
När samma värde kan förekomma flera gånger och ni behöver räkna antalet giltiga par (inte bara avgöra om de finns) lagrar ni frekvensantal i map:en. För par där båda elementen är lika är antalet par från frekvensen f lika med f*(f-1)//2. För par där de två elementen skiljer sig åt multiplicerar ni deras frekvenser. På så sätt kan alla giltiga par räknas i 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)...Känna igen varianter av Two-Sum-mönstret
Two-sum-mönstret förekommer i många skepnader. Känn igen det när ett problem ber er hitta två eller fler element som uppfyller ett numeriskt samband (summa, produkt eller differens). Grundstrategin är alltid att fixera ett element och sedan hitta dess komplement i en förberäknad struktur (hash map eller sorterad array + pekare). Utvidga till k-sum genom att fixera k-2 element med nästlade loopar och tillämpa basfallet.
# 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')Kommunikation om Two-Sum i intervjun
När two-sum dyker upp i en intervju ska ni tänka högt: ”Jag behöver två tal vars summa är target. För varje tal x måste jag kontrollera om target-x finns. Det kan jag göra i O(1) med en hash map, vilket ger en total tidsåtgång på O(n) och utrymmesåtgång på O(n). Alternativt, om arrayen var sorterad, kunde jag använda två pekare med O(1) utrymme.” Ange båda tillvägagångssätten och fråga om det finns begränsningar för minnesanvändningen innan ni väljer.
Snabb kontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde ni er: two-sum använder en hash map för att kontrollera om komplementet finns i O(1), vilket ger O(n) totalt, för sorterade arrayer ger två pekare O(1) utrymme, och three-sum och four-sum reduceras till two-sum genom sortering och nästlade loopar, med körtider på O(n²) respektive O(n³). Härnäst utforskar vi mönster för frekvensräkning och gruppering med defaultdict och Counter.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Two-sum och dess många varianter” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Two-sum och dess många varianter”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Two-sum och dess många varianter”?
Lös two-sum, three-sum, four-sum och two-sum with sorted array med hash maps och två pekare och jämför tids- och utrymmeskostnader. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Two-sum och dess många varianter”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Hashfunktioners interna delar och kollisionshantering
- Two-sum och dess många varianter
- Frekvensräkning och gruppering
- Längsta följden av på varandra följande tal och LRU-cache