Algorithmusgratis

Paarsumme per Brute Force

Probiere jedes Paar aus, um zwei Zahlen mit einer Zielsumme zu finden. Einfach, aber O(n²).

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

// Schritt für Schritt

Schritt 1 / 10

1function twoSumBrute(nums, target) {2  for (let i = 0; i < nums.length; i++) {3    for (let j = i + 1; j < nums.length; j++) {4      if (nums[i] + nums[j] === target) return [i, j];5    }6  }7  return null;8}

target: = 10
checks: = 1

1 + 3 = 4, nicht 10. Bisherige Prüfungen: 1.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

So funktioniert es

Zwei verschachtelte Schleifen probieren jedes Paar: die erste Zahl mit jeder späteren, dann die zweite und so weiter. Bei n Elementen sind das etwa n²/2 Paare; ein doppelt so großes Array bedeutet also ungefähr viermal so viel Arbeit. Das ist O(n²). Vergleiche das mit der Lektion zu zwei Zeigern, die dasselbe Problem auf einem sortierten Array in einem Durchlauf löst.