Two-Sum und seine vielen Varianten
Lösen Sie two-sum, three-sum, four-sum und two-sum with sorted array mit Hash-Maps und zwei Zeigern und vergleichen Sie Zeit- und Speicherbedarf.
Two-Sum und seine vielen Varianten ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Two-Sum: Das klassische Interviewproblem
LeetCode 1 'Two Sum': Bei einem unsortierten Array und einem Zielwert sollen Sie die Indizes zweier Elemente zurückgeben, deren Summe dem Zielwert entspricht. Der Brute-Force-Ansatz mit O(n²) prüft alle Paare. Der optimale Ansatz mit O(n) verwendet eine Hash-Map: Prüfen Sie für jedes Element x, ob target - x bereits in der Map vorhanden ist. Falls ja, geben Sie das Indexpaar zurück. Falls nein, speichern Sie x und seinen Index in der Map.
Two-Sum ist oft die allererste Aufgabe in einem Interview – wer sie sicher beherrscht, signalisiert, für schwierigere Aufgaben bereit zu sein.
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]Warum die Hash-Map bei Two-Sum funktioniert
Die Hash-Map speichert jedes bisher gesehene Element. Wenn Sie das Element x verarbeiten und target - x in der Map vorhanden ist, bilden diese beiden Elemente ein gültiges Paar. Entscheidend ist, dass das Komplement geprüft wird, bevor x gespeichert wird. Dadurch wird verhindert, dass ein einzelnes Element mit sich selbst gepaart wird (wenn beispielsweise x == target/2 gilt, erfolgt die Prüfung der Map vor dem Speichern von x, sodass es nur dann gefunden wird, wenn zwei Kopien vorhanden sind).
# 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 in einem sortierten Array (zwei Zeiger)
Wenn das Array bereits sortiert ist und Sie die Indizes der Werte (nicht die ursprünglichen Indizes) benötigen, verwenden Sie das Zwei-Zeiger-Verfahren: Starten Sie mit den Zeigern left und right an den entgegengesetzten Enden. Wenn die Summe dem Zielwert entspricht, geben Sie das Ergebnis zurück. Wenn die Summe zu klein ist, verschieben Sie left nach rechts. Wenn sie zu groß ist, verschieben Sie right nach links. Der Zeitaufwand beträgt O(n), der zusätzliche Speicherbedarf O(1) – besser als beim Hash-Map-Ansatz, wenn das Array sortiert ist und der Speicher begrenzt ist.
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': Finden Sie alle eindeutigen Tripel, deren Summe null ergibt. Sortieren Sie das Array, wählen Sie nacheinander ein Element fest aus und wenden Sie auf das verbleibende sortierte Teilarray das Zwei-Zeiger-Verfahren an. Überspringen Sie doppelte Werte, um doppelte Tripel zu vermeiden. Zeitaufwand: O(n²) – optimal für dieses Problem, da die Ausgabe selbst O(n²) Tripel enthalten kann.
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': Finden Sie alle eindeutigen Quadruple, deren Summe dem Zielwert entspricht. Erweitern Sie Three-Sum: Wählen Sie mit zwei verschachtelten Schleifen zwei Elemente fest aus (und überspringen Sie Duplikate), anschließend wenden Sie auf das innere Teilarray das Zwei-Zeiger-Verfahren an. Zeitaufwand: O(n³). Für k-Sum gilt allgemein: Rekursion k-2-mal anwenden und anschließend zwei Zeiger verwenden, was einen Zeitaufwand von O(n^(k-1)) ergibt.
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 mit der kleinsten Abweichung vom Zielwert
Eine häufige Variante: Finden Sie das Paar, dessen Summe dem Zielwert am nächsten kommt (die Summe muss nicht genau dem Zielwert entsprechen). Sortieren Sie das Array und verwenden Sie zwei Zeiger. Speichern Sie die bisher nächstgelegene Summe und aktualisieren Sie sie, sobald Sie ein Paar mit einer kleineren absoluten Differenz zum Zielwert finden. Dieser Ansatz mit O(n log n) ist nach dem Sortieren unkompliziert.
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 mit mehreren Paaren (alle Paare)
Um alle Paare zu finden, deren Summe einem Zielwert entspricht, sortieren Sie das Array und verwenden Sie zwei Zeiger, um alle Paare zu sammeln. Nachdem Sie ein gültiges Paar gefunden haben, überspringen Sie an beiden Enden die Duplikate, bevor Sie fortfahren. Das ergibt O(n log n) für das Sortieren plus O(n) für den Durchlauf – insgesamt O(n log n). Auch eine Hash-Map zum Sammeln der Paare ist möglich, erfordert aber einen sorgfältigen Umgang mit Duplikaten.
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)]Paare mit einer Summe kleiner als K zählen
Eine weitere Variante: Zählen Sie, wie viele Paare eine Summe kleiner als k haben. Sortieren Sie das Array und verwenden Sie zwei Zeiger. Wenn nums[lo] + nums[hi] < k gilt, sind alle Paare (lo, lo+1), (lo, lo+2), ..., (lo, hi) gültig – insgesamt hi - lo Paare. Erhöhen Sie lo. Andernfalls verringern Sie hi. Der Gesamtzeitaufwand beträgt O(n log n) für das Sortieren plus O(n) für das Zählen.
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 mit einer Hash-Map: Umgang mit Duplikaten
Wenn derselbe Wert mehrmals vorkommen kann und Sie die Anzahl gültiger Paare (nicht nur ihre Existenz) benötigen, speichern Sie Häufigkeiten in der Map. Für Paare, deren beide Elemente gleich sind, beträgt die Anzahl der Paare bei einer Häufigkeit f f*(f-1)//2. Bei Paaren mit unterschiedlichen Elementen multiplizieren Sie deren Häufigkeiten. So können Sie alle gültigen Paare in O(n) zählen.
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)...Varianten des Two-Sum-Musters erkennen
Das Two-Sum-Muster tritt in vielen Varianten auf. Erkennen Sie es, wenn eine Aufgabe verlangt, zwei oder mehr Elemente zu finden, die eine numerische Beziehung erfüllen (Summe, Produkt oder Differenz). Die grundlegende Strategie lautet immer: Wählen Sie ein Element fest aus und suchen Sie sein Komplement in einer vorberechneten Datenstruktur (Hash-Map oder sortiertem Array mit Zeiger). Erweitern Sie das Verfahren auf k-Sum, indem Sie k-2 Elemente mit verschachtelten Schleifen festlegen und anschließend den Basisfall anwenden.
# 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 im Interview bei Two-Sum
Wenn Two-Sum in einem Interview vorkommt, erläutern Sie Ihre Überlegungen laut: „Ich brauche zwei Zahlen, deren Summe dem Zielwert entspricht. Für jede Zahl x muss ich prüfen, ob target-x vorhanden ist. Mit einer Hash-Map kann ich diese Prüfung in O(1) durchführen, was insgesamt O(n) Zeit und O(n) zusätzlichen Speicher benötigt. Wenn das Array sortiert wäre, könnte ich alternativ zwei Zeiger mit O(1) zusätzlichem Speicher verwenden.“ Nennen Sie beide Ansätze und fragen Sie nach Speicherbeschränkungen, bevor Sie sich entscheiden.
Schnelltest
Testen Sie Ihr Verständnis der in dieser Lektion behandelten Konzepte aus Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: two-sum verwendet eine Hashmap, um in O(1) zu prüfen, ob das Komplement existiert, und erreicht damit insgesamt O(n), bei sortierten Arrays erreichen zwei Zeiger O(1) zusätzlichen Speicherplatz und three-sum und four-sum lassen sich durch Sortieren und verschachtelte Schleifen auf two-sum reduzieren und laufen jeweils in O(n²) bzw. O(n³). Als Nächstes betrachten wir Muster zum Zählen von Häufigkeiten sowie das Gruppieren mit defaultdict und Counter.
Häufig gestellte Fragen
Ist die Lektion „Two-Sum und seine vielen Varianten“ kostenlos?
Ja — der vollständige Text von „Two-Sum und seine vielen Varianten“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Two-Sum und seine vielen Varianten“?
Lösen Sie two-sum, three-sum, four-sum und two-sum with sorted array mit Hash-Maps und zwei Zeigern und vergleichen Sie Zeit- und Speicherbedarf. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Two-Sum und seine vielen Varianten“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Interna von Hash-Funktionen und Kollisionsbehandlung
- Two-Sum und seine vielen Varianten
- Häufigkeiten zählen und gruppieren
- Längste aufeinanderfolgende Sequenz und LRU-Cache