Two-Sum-Algorithmus in Python
Two Sum zeigt, wie zusätzlicher Speicher eine verschachtelte Suche vermeiden kann.
Was ist Two-Sum-Algorithmus?
Two Sum zeigt, wie zusätzlicher Speicher eine verschachtelte Suche vermeiden kann.
Finde zwei Werte, deren Summe einem Zielwert entspricht.
Wann wird dieser Ansatz verwendet?
- Algorithmen und Datenstrukturen anhand von ausführbarem Code verstehen.
- Die einzelnen Verarbeitungsschritte und Randfälle nachvollziehen.
- Laufzeit und Speicherbedarf verschiedener Lösungswege vergleichen.
Beispielcode
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))Erwartete Ausgabe
[0, 1]So funktioniert es
Eine Hash-Tabelle speichert bereits besuchte Werte. Das benötigte Komplement kann dadurch in O(1) nachgeschlagen werden; insgesamt O(n) Zeit und O(n) Speicher.
Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.
Übungsaufgaben
Verändere Eingaben und Randfälle, bevor du die Lösung mit größeren Datenmengen testest.
- Teste leere Eingaben, ein Element und doppelte Werte.
- Gib den Zustand nach jedem Schritt aus.
- Vergleiche Laufzeit und Speicherbedarf mit einem alternativen Verfahren.