Algorithmen und Datenstrukturen · Junior · Frage 62 von 75
Two Sum: finde in einem unsortierten Array zwei Zahlen, deren Summe target ergibt. Was ist der O(n)-Ansatz?
- 1Das Array sortieren und seine zwei kleinsten Elemente liefern
- 2Jedes mögliche Paar mit zwei verschachtelten Schleifen probieren
- 3Prüfen, ob
target - xin einer Map der bisher gesehenen Zahlen steht
Antwort zeigen
Richtige Antwort: Prüfen, ob target - x in einer Map der bisher gesehenen Zahlen steht
Erklärung
Ein Durchlauf: wurde target - x schon gesehen, ist das Paar gefunden; sonst merke dir x und seinen Index. Jedes Paar zu probieren ist O(n²). Sortieren ergibt O(n log n) und verliert die ursprünglichen Indizes.