Algorithmusgratis

Zwei Zeiger

Finde in einem sortierten Array ein Paar, das eine Zielsumme ergibt, in einem einzigen Durchlauf.

Zeit: O(n)
Speicher: O(1)

// Schritt für Schritt

Schritt 1 / 11

1function twoSum(nums, target) {2  let lo = 0, hi = nums.length - 1;3  while (lo < hi) {4    const sum = nums[lo] + nums[hi];5    if (sum === target) return [lo, hi];6    if (sum < target) lo++;7    else hi--;8  }9  return null;10}

target: = 10

1lo
3
4
6
8
11hi

Das Array ist sortiert. lo startet am linken Ende, hi am rechten.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

So funktioniert es

Setze je einen Zeiger an beide Enden eines sortierten Arrays. Ist die Summe zu klein, rückt der linke Zeiger nach rechts; ist sie zu groß, rückt der rechte nach links. Jeder Schritt schließt eine ganze Gruppe von Paaren aus, deshalb braucht die Suche lineare Zeit, statt jedes Paar zu prüfen.