Overview
Zwei Indizes finden, deren Werte zusammen die Zielzahl ergeben – mit Hash Map in O(n).
Analogy
Auf einer Party jeden Namen merken; wenn man jemanden trifft, prüfen ob das Komplement bereits gesehen wurde.
Step-by-step
- Erstelle seen = {}.
- Für jedes (i, num) in enumerate(nums):
- complement = target - num.
- Wenn complement in seen: return [seen[complement], i].
- Sonst: seen[num] = i.
Visual
[2,7,11,15], target=9 → sehe 2(komp=7,nein) → sehe 7(komp=2,ja) → [0,1]
Common mistakes
- Falscher Rückgabe-Index (gespeicherten Index zurückgeben, nicht den des Komplements).
- Verschachteltes O(n²) verwenden statt O(n) mit Hash Map.
Practice questions
- Dreiersumme (3Sum): Sortierung + Zwei-Zeiger.
- Alle Paare zurückgeben (nicht nur das erste), Duplikate behandeln.