ENDEAR
Kostenlos starten
Algorithmusgratis

Two Sum mit einer Hashmap

Finde in einem Durchlauf zwei Zahlen mit einer Zielsumme, auch in einem unsortierten Array.

Zeit
O(n)
Speicher
O(n)

// Schritt für Schritt

Schritt 1 / 9
1function twoSum(nums, target) {2  const seen = new Map();3  for (let i = 0; i < nums.length; i++) {4    const need = target - nums[i];5    if (seen.has(need)) return [seen.get(need), i];6    seen.set(nums[i], i);7  }8  return null;9}
target
= 9
  1. 3
  2. 8
  3. 2
  4. 7
  5. 5
seenleer

Wir starten mit einer leeren Map seen. Sie merkt sich jede Zahl und ihren Index.

So funktioniert es

Berechne für jede Zahl den Partner, den sie bis zum Ziel braucht, und frag eine Hashmap, ob dieser Partner schon vorkam. Nachschlagen kostet im Schnitt O(1), deshalb reicht ein Durchlauf: O(n) Zeit. Der Preis ist Speicher: Die Map kann bis zu n Zahlen enthalten, also O(n) Speicher. Speicher gegen Zeit zu tauschen ist einer der häufigsten Kniffe bei Programmieraufgaben.

Dieses Muster erkennen üben →