Algorithmen und Datenstrukturen · Middle · Frage 19 von 75
Two Sum auf einem sortierten Array: was ist der O(n)-Ansatz ohne zusätzlichen Speicher?
- 1Für jedes Element binär nach seinem Partner suchen
- 2Vor der Suche alle Elemente in eine Hash-Map legen
- 3Zwei Zeiger von beiden Enden, bewegt nach Vergleich der Summe
Antwort zeigen
Richtige Antwort: Zwei Zeiger von beiden Enden, bewegt nach Vergleich der Summe
Erklärung
Die Sortierung sagt, welcher Zeiger sich bewegen muss: den linken Wert zu erhöhen hebt die Summe, den rechten zu senken senkt sie. Eine Hash-Map geht auch in O(n), braucht aber O(n) Speicher.