Two Sum II: Sorted Input

Q: Warum funktionieren zwei Zeiger bei Two Sum für ein sortiertes Array?

Wenn die Summe der beiden Enden zu klein ist, ist der linke Wert für jeden noch möglichen Partner zu klein, denn das rechte Ende ist der größte davon. Du kannst ihn endgültig verwerfen. Dasselbe Argument verwirft den rechten Wert, wenn die Summe zu groß ist. Das Antwortpaar wird nie verworfen, daher enden die Zeiger darauf.

Q: Wie hoch ist die Zeitkomplexität von Two Sum II?

Die Lösung mit zwei Zeigern benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz: Bei jedem Schritt wird ein Zeiger nach innen bewegt, und nach höchstens n-1 Schritten treffen sie aufeinander. Eine binäre Suche nach jedem passenden Element benötigt O(n log n) , und das Überprüfen jedes Paars benötigt O(n²) .

Q: Warum nicht eine Hash-Map wie bei der ersten Two Sum verwenden?

Eine Hashmap funktioniert ebenfalls und läuft in O(n) Zeit, speichert aber bis zu n Werte. Durch die sortierte Reihenfolge ist dieser Speicher unnötig: Die beiden Zeiger wissen allein anhand der Summe, in welche Richtung sie sich bewegen müssen. Interviewer stellen diese Variante, um zu sehen, ob du die vorgegebene Reihenfolge nutzt.

Q: Wann ist die binäre Suche hier die bessere Wahl?

Wenn ein Wert feststeht und du nur noch seinen Partner brauchst. Wenn numbers[0] im Paar enthalten sein muss, findet eine binäre Suche den anderen Index in O(log n) . Um ein unbekanntes Paar zu finden, ist die Suche mit zwei Zeigern schneller als n einzelne Suchvorgänge.

LeichtZwei Zeiger Binäre Suche

+10

Du erhältst ein Array aus Ganzzahlen numbers, das in nicht absteigender Reihenfolge sortiert ist, und eine Ganzzahl target. Genau ein Paar verschiedener Positionen enthält zwei Werte, deren Summe target ergibt. Gib diese beiden Positionen als 0-basierte Indizes zurück, zuerst den kleineren Index.

Funktion

twoSumSorted(numbers: integer-array, target: integer) → integer-array

numbersinteger-array: das sortierte Array aus ganzen Zahlen
targetinteger: Die Summe der beiden Werte muss erreichen
Gibt zurückinteger-array: die beiden 0-basierten Indizes [i, j] mit i < j und numbers[i] + numbers[j] == target

Einschränkungen

2 ≤ numbers.length ≤ 10⁴
-5 × 10⁸ ≤ numbers[i] ≤ 5 × 10⁸
-10⁹ ≤ target ≤ 10⁹
numbers ist in nicht absteigender Reihenfolge sortiert.
Genau ein Indexpaar i < j erfüllt numbers[i] + numbers[j] == target.

Beispiele

Eingabe: numbers = [-4, 1, 3, 8, 12]target = 9
Ausgabe: [1, 3]
Erklärung: 1 steht am Index 1 und 8 am Index 3, und 1 + 8 = 9. Kein anderes Paar ergibt 9: zum Beispiel ist -4 + 12 = 8.

+13 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du es in O(n)-Zeit mit O(1) zusätzlichem Speicher lösen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine Hash-Map löst die unsortierte Variante in einem Durchlauf, benötigt aber O(n) Speicher. Hier ist das Array sortiert, und anhand dieser Reihenfolge weißt du, in welche Richtung du gehen musst. Setze an jedes Ende einen Zeiger. Ist die Summe zu klein, kann nur ein größerer linker Wert helfen; ist sie zu groß, kann nur ein kleinerer rechter Wert helfen. Bei jedem Schritt scheidet ein Wert endgültig aus, sodass ein Durchlauf das Paar ohne zusätzlichen Speicher findet.

Prüfe jedes Paar

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Probiere jedes Paar von Positionen i < j aus und prüfe, ob numbers[i] + numbers[j] gleich target ist. Da i von links läuft und j direkt danach beginnt, hat das erste gefundene Paar bereits den kleineren Index an erster Stelle.

Das ist korrekt, nutzt aber die Sortierung nicht aus. Bei n = 10^4 gibt es etwa 5 × 10^7 Paare, und wenn sich die Antwort nahe am Ende des Arrays befindet, prüfst du fast alle davon. Das ist für die großen Tests zu langsam.

Algorithmus

Durchlaufe i für jeden Index.
Durchlaufe j von i+1 bis zum letzten Index.
Wenn numbers[i] + numbers[j] gleich target ist, gib [i, j] zurück.

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i, j]
    return []

Binäre Suche für jeden Partner

Idee

Sobald du den ersten Wert numbers[i] festgelegt hast, kennst du seinen Partner genau: target - numbers[i]. Der Teil des Arrays rechts von i ist sortiert, daher kann die binäre Suche in O(log n) Schritten feststellen, ob sich dieser Partner darin befindet.

Für [-4, 1, 3, 8, 12] und target = 9: Bei i = 0 wäre der Partner 13, aber dieser Wert fehlt. Bei i = 1 ist der Partner 8, und die Suche findet ihn an Index 3. Die Antwort lautet [1, 3].

Wenn du nur rechts von i suchst, steht der kleinere Index zuerst und ein Wert kann nicht mit sich selbst gepaart werden. Das Paar ist eindeutig, daher kommt der Partnerwert in diesem Bereich höchstens einmal vor, und jeder Treffer ist die Antwort. Insgesamt: n Suchen mit jeweils O(log n).

Algorithmus

Durchlaufe die Schleife mit i von 0 bis n-2.
Berechne need = target - numbers[i].
Führe eine binäre Suche nach need in den Indizes i+1 bis n-1 durch.
Wenn du need bei mid findest, gib [i, mid] zurück.

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n - 1):
        need = target - numbers[i]
        lo, hi = i + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if numbers[mid] == need:
                return [i, mid]
            if numbers[mid] < need:
                lo = mid + 1
            else:
                hi = mid - 1
    return []

Zwei Zeiger von beiden Enden

Idee

Beginne mit left = 0 und right = n-1 und betrachte numbers[left] + numbers[right]. Wenn die Summe target entspricht, bist du fertig. Ist sie zu klein, kann numbers[left] nicht Teil der Antwort sein: Selbst zusammen mit dem größten noch verfügbaren Wert ist die Summe zu klein. Bewege also left nach rechts. Ist die Summe zu groß, kann auch numbers[right] nicht dazugehören, da selbst der kleinste verbleibende Partner eine zu große Summe ergibt. Bewege also right nach links.

Bei jedem Schritt wird ein Wert verworfen, der niemals Teil des Paares sein kann, während das Paar selbst nie verworfen wird. Die Zeiger treffen nach höchstens n-1 Schritten aufeinander. Die Suche hat also eine Laufzeit von O(n) und verwendet zwei Variablen.

Bei [-4, 1, 3, 8, 12] mit target = 9: -4 + 12 = 8 ist zu klein, also wird left auf Index 1 gesetzt. Dann ist 1 + 12 = 13 zu groß, also wird right auf Index 3 gesetzt. Nun gilt 1 + 8 = 9, und die Antwort ist [1, 3].

Algorithmus

Setze left auf 0 und right auf n-1.
Berechne, solange left < right gilt, total = numbers[left] + numbers[right].
Gib [left, right] zurück, wenn total gleich target ist.
Ist total kleiner, addiere 1 zu left; ist es größer, ziehe 1 von right ab.

def twoSumSorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1  # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return []

Stolperfallen und Grenzfälle

Die Zwei-Zeiger-Schleife ist kurz, deshalb verstecken sich die Fehler in den Details drumherum.

1-basierte Positionen zurückgeben. Diese Version erwartet 0-basierte Indizes: Für [-4, 1, 3, 8, 12] und target = 9 lautet die Antwort [1, 3], nicht [2, 4]. Ziehe in Lua und R vor der Rückgabe 1 ab.
Mit left <= right durchlaufen. Wenn sich die Zeiger treffen, würde die Summe denselben Wert zweimal verwenden.
Den falschen Zeiger verschieben. Eine zu kleine Summe braucht einen größeren Wert, und nur left kann einen liefern.
Doppelte Werte ablehnen. Bei [2, 2, 5, 7] mit target = 4 werden beide 2er verwendet, die sich an unterschiedlichen Positionen befinden.
Überlauf. Die Grenzwerte sorgen hier dafür, dass jede Summe innerhalb einer 32-Bit-Ganzzahl bleibt. Könnten die Werte 10^9 erreichen, addiere sie mit einem 64-Bit-Typ.

Häufige Fragen4

Warum funktionieren zwei Zeiger bei Two Sum für ein sortiertes Array?

Wenn die Summe der beiden Enden zu klein ist, ist der linke Wert für jeden noch möglichen Partner zu klein, denn das rechte Ende ist der größte davon. Du kannst ihn endgültig verwerfen. Dasselbe Argument verwirft den rechten Wert, wenn die Summe zu groß ist. Das Antwortpaar wird nie verworfen, daher enden die Zeiger darauf.

Wie hoch ist die Zeitkomplexität von Two Sum II?

Die Lösung mit zwei Zeigern benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz: Bei jedem Schritt wird ein Zeiger nach innen bewegt, und nach höchstens n-1 Schritten treffen sie aufeinander. Eine binäre Suche nach jedem passenden Element benötigt O(n log n), und das Überprüfen jedes Paars benötigt O(n²).

Warum nicht eine Hash-Map wie bei der ersten Two Sum verwenden?

Eine Hashmap funktioniert ebenfalls und läuft in O(n) Zeit, speichert aber bis zu n Werte. Durch die sortierte Reihenfolge ist dieser Speicher unnötig: Die beiden Zeiger wissen allein anhand der Summe, in welche Richtung sie sich bewegen müssen. Interviewer stellen diese Variante, um zu sehen, ob du die vorgegebene Reihenfolge nutzt.

Wann ist die binäre Suche hier die bessere Wahl?

Wenn ein Wert feststeht und du nur noch seinen Partner brauchst. Wenn numbers[0] im Paar enthalten sein muss, findet eine binäre Suche den anderen Index in O(log n). Um ein unbekanntes Paar zu finden, ist die Suche mit zwei Zeigern schneller als n einzelne Suchvorgänge.

Python

def twoSumSorted(numbers, target):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

numbers = [-4, 1, 3, 8, 12]
target = 9

Erwartet

[1, 3]

Two Sum II: Sorted Input

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Prüfe jedes Paar

Binäre Suche für jeden Partner

Zwei Zeiger von beiden Enden

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben