Python-Algorithmen

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.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

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.

Vom Einkauf mit Budget zum Code
complement = target - value🤔 Der Preis, der noch fehlt
if complement in seen:📋 Steht dieser Preis schon auf meinem Zettel?
return [seen[complement], index]🛍️ Paar gefunden: beide Positionen
seen[value] = index✍️ Diesen Preis und seine Position notieren, dann weiter
Den fehlenden Preis nachschlagen, statt jedes Paar zu prüfen.
In einem Satz

Das 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

  1. complement = target - value ist der Wert, der das Paar vervollständigen würde.
  2. seen ordnet jedem schon besuchten Wert seinen Index zu, sodass Nachschlagen schnell geht.
  3. if complement in seen: findet den Partner unter den früheren Werten.
  4. seen[value] = index wird erst nach der Prüfung gespeichert, sodass ein Wert nie mit sich selbst gepaart wird.
  5. 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

Code ausführen →
main.py
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))
Run-Button für dieses Beispiel erstellen

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.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

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.

Problem
seen[value] = index
if target - value in seen:
Lösung
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