Das Two-Sum-Problem in Python
In dieser Lektion löst du das Two-Sum-Problem und findest mit einem einzigen Durchlauf durch die Liste zwei Elemente, deren Summe einen vorgegebenen Wert ergibt.
Einführung
Das Problem
Du hast eine Liste von Preisen und ein Budget: Welche zwei Artikel kosten genau das Budget? Jedes Paar zu prüfen funktioniert, braucht aber etwa n² / 2 Vergleiche. Wenn du dir merkst, was du schon gesehen hast, geht es in einem Durchgang.
Stell es dir so vor
Two Sum ist wie Einkaufen mit einem genauen Budget. Bei jedem Preisschild rechnest du aus, wie viel noch fehlt, und schaust auf deinen Notizzettel: Habe ich schon einen Artikel mit genau diesem Preis gesehen? Wenn ja, hast du das Paar gefunden. Wenn nicht, notierst du diesen Preis und wo du ihn gesehen hast, und gehst weiter.
complement = target - value🤔 Der Preis, der noch fehltif complement in seen:📋 Steht dieser Preis schon auf meinem Zettel?return [seen[complement], index]🛍️ Paar gefunden: beide Positionenseen[value] = index✍️ Diesen Preis und seine Position notieren, dann weiterDas Two-Sum-Problem fragt nach den Positionen zweier Zahlen in einer Liste, die zusammen einen Zielwert ergeben. Ein Dictionary der gesehenen Werte löst es in einem Durchgang, also in O(n) Zeit.
Das Wichtigste
complement = target - valueist der Wert, der das Paar vervollständigen würde.seenordnet jedem schon besuchten Wert seinen Index zu, sodass Nachschlagen schnell geht.if complement in seen:findet den Partner unter den früheren Werten.seen[value] = indexwird erst nach der Prüfung gespeichert, sodass ein Wert nie mit sich selbst gepaart wird.- Für 9 findet der Wert 7 seinen Partner 2 an Index 0, das ergibt
[0, 1].
Wann verwendet man das?
- Paare mit einer gegebenen Summe oder Differenz finden.
- Lernen, mit einer Hashtabelle Speicher gegen Geschwindigkeit zu tauschen.
- Eine sehr häufige Interviewfrage und die Grundlage für 3-Sum und ähnliche Probleme.
Wann du es nicht brauchst
- Sortierte Eingabe bei knappem Speicher: Zwei Zeiger von beiden Enden brauchen keinen zusätzlichen Speicher.
- Du brauchst jedes Paar, nicht nur eins: Sammle die Ergebnisse, statt beim ersten Treffer zurückzugeben.
Beispielcode
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
print(two_sum([2, 7, 11, 15], 9))
Ergebnis der Ausführung
[0, 1]
Erklärung des Codes
Das Dictionary seen speichert die bereits durchlaufenen Werte zusammen mit ihrer Position. Für jedes Element berechnet das Programm die Ergänzung complement = target - value und prüft, ob sie schon in seen steht. Da das Nachschlagen in einem Dictionary nur O(1) kostet, läuft der ganze Algorithmus in O(n) und braucht O(n) zusätzlichen Speicher.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungen zur Vertiefung
Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Vor der Prüfung speichern
Ein Wert kann sich dann mit sich selbst paaren, etwa 3 + 3 = 6 mit nur einer 3.
seen[value] = index
if target - value in seen:
if target - value in seen:
return [seen[target - value], index]
seen[value] = index
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
Alle Challenges