3Sum

+10

Du erhältst eine Liste von Ganzzahlen nums. Finde jedes Tripel [a, b, c] aus Werten, die von drei verschiedenen Positionen in nums stammen, mit a + b + c = 0. Schreibe jedes Tripel in nicht absteigender Reihenfolge (a ≤ b ≤ c) und liste jedes unterschiedliche Tripel nur einmal auf, auch wenn es durch mehrere Positionsauswahlen entsteht. Gib die Tripel zurück, sortiert nach ihrem ersten Wert und dann nach ihrem zweiten.

Funktion

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: die Liste der ganzen Zahlen mit mindestens drei Elementen
Gibt zurückinteger-2d-array: jedes unterschiedliche Tripel, dessen Summe 0 ergibt, jedes in nicht absteigender Reihenfolge, die Liste sortiert

Einschränkungen

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Mindestens ein Tripel ergibt insgesamt 0.
Zwei Tripel sind gleich, wenn sie dieselben drei Werte enthalten.

Beispiele

Eingabe: nums = [-2, 0, 1, 1, -1, 2]
Ausgabe: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Erklärung: -2 + 0 + 2, -2 + 1 + 1 und -1 + 0 + 1 ergeben alle 0. [-2, 1, 1] kann den Wert 1 zweimal verwenden, da die 1 an zwei Positionen steht, während [-1, 0, 1] mit einer der beiden 1en gebildet werden kann, aber nur einmal vorkommt.

Eingabe: nums = [0, 0, 0, 0]
Ausgabe: [[0, 0, 0]]
Erklärung: Je drei der vier Nullen ergeben zusammen 0. Es gibt vier Möglichkeiten, die Positionen auszuwählen, aber sie ergeben alle dasselbe Tripel, daher enthält die Antwort [0, 0, 0] nur einmal.

+15 versteckte Tests beim Einreichen

Weiterführende Frage

Dasselbe Muster löst 4Sum: Fixiere zwei Werte und setze für den Rest zwei Zeiger ein. Kannst du es in O(n³) schreiben und auf jeder Ebene die Regeln zum Umgang mit Duplikaten korrekt einhalten?

Tipps

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

0 von 3 geöffnet

Lösung

Zwei Dinge machen 3Sum schwieriger, als es aussieht. Jedes Tripel zu überprüfen, kostet O(n³), und die Antwort muss jedes Tripel genau einmal enthalten, auch wenn Werte mehrfach vorkommen. Sortieren löst beides: Gleiche Werte stehen nebeneinander, sodass du Wiederholungen überspringst, indem du benachbarte Werte vergleichst. Sobald der kleinste Wert feststeht, bilden die beiden anderen ein Paarsummenproblem in einer sortierten Liste, das sich mit zwei Zeigern in einem Durchlauf lösen lässt.

Probiere jedes Tripel aus

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

Idee

Sortiere die Liste zuerst. Dann ergeben je drei Positionen i < j < k Werte, die bereits der Reihenfolge nach sortiert sind, nums[i] ≤ nums[j] ≤ nums[k], sodass ein Tripel in dem Moment korrekt geschrieben ist, in dem du es findest. Drei verschachtelte Schleifen durchlaufen jede Positionsauswahl, sodass kein Tripel übersehen werden kann.

Als Nächstes kommen Wiederholungen. Das erste Beispiel sortiert sich zu [-2, -1, 0, 1, 1, 2], und [-1, 0, 1] kann seine 1 entweder von Index 3 oder Index 4 nehmen. Daher überspringt jede Schleife eine Position, deren Wert dem Wert entspricht, den dieselbe Schleife zuvor ausprobiert hat. Jede Schleife probiert dann jeden unterschiedlichen Wert genau einmal aus, und jedes unterschiedliche Tripel kommt genau einmal und bereits in sortierter Reihenfolge heraus. Das Überspringen vergleicht nur mit der vorherigen Position innerhalb derselben Schleife, sodass [-2, 1, 1] weiterhin beide Einsen verwendet.

Das Problem ist der Aufwand. Es gibt etwa n³/6 Tripel: Bei 3000 Zahlen sind das 4.5 × 10^9 Summen, weit mehr, als ein Zeitlimit zulässt.

Algorithmus

Sortiere nums.
Durchlaufe die Positionen mit i und überspringe i, wenn nums[i] gleich nums[i-1] ist.
Durchlaufe darin j ab i+1 und überspringe j, wenn j > i+1 und nums[j] gleich nums[j-1] ist.
Durchlaufe darin k ab j+1 mit derselben Überspringregel und speichere [nums[i], nums[j], nums[k]], wenn die drei Werte zusammen 0 ergeben.
Gib die Tripel in der Reihenfolge zurück, in der du sie gefunden hast. Sie sind bereits sortiert.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Fixiere einen Wert, finde das Paar mit einer Hashtabelle

Idee

Sobald der erste Wert nums[i] feststeht, brauchst du zwei spätere Werte, die zusammen -nums[i] ergeben. Das ist Two Sum. Gehe mit j rechts von i entlang und speichere die Werte, an denen du vorbeigekommen bist, in einer Menge. Bei jedem j ist der fehlende Wert need = -nums[i] - nums[j]. Wenn need in der Menge ist, ergibt [nums[i], need, nums[j]] zusammen 0. Eine Suche in einer Menge kostet im Durchschnitt O(1), daher kostet ein i O(n) und die gesamte Suche O(n²).

Das Sortieren übernimmt weiterhin die Verwaltung. Überspringe ein i, dessen Wert dem vorherigen entspricht. Bewege j nach einem Treffer an allen Kopien von nums[j] vorbei: Sind der erste und dritte Wert festgelegt, ist auch der mittlere festgelegt, sodass eine weitere Kopie nur dasselbe Tripel wiederholen könnte. Da need von einer früheren Position der sortierten Liste stammt, gilt need ≤ nums[j] und das Tripel ist geordnet. Du kannst außerdem abbrechen, sobald nums[i] > 0: Die beiden folgenden Werte sind mindestens genauso groß, sodass die Summe nicht 0 ergeben kann.

Ein Detail: Wenn sich j nach rechts bewegt, wird nums[j] größer und need kleiner, sodass die Tripel für ein i mit abnehmendem mittlerem Wert entstehen. In [-2, -1, 0, 1, 1, 2] mit i = 0 findest du [-2, 1, 1] beim zweiten 1 und dann [-2, 0, 2] bei der 2. Drehe jede Gruppe um, bevor du sie zur Antwort hinzufügst. Die C- und R-Versionen markieren bereits gesehene Werte in einem nach Werten indizierten Array statt in einer Hash-Menge. Das funktioniert, weil jeder Wert innerhalb von ±10^5 liegt.

Algorithmus

Sortiere nums.
Beende die Schleife für jedes i, sobald nums[i] > 0 gilt, und überspringe i, wenn nums[i] gleich nums[i-1] ist.
Erstelle eine leere Menge. Berechne für jedes j ab i+1 need = -nums[i] - nums[j]. Wenn need in der Menge ist, speichere [nums[i], need, nums[j]] und gehe bei j über die Kopien von nums[j] hinweg.
Füge nums[j] zur Menge hinzu und fahre mit dem nächsten j fort.
Kehre die für dieses i gefundenen Tripel um und füge sie der Antwort hinzu.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Sortieren und zwei Zeiger verwenden

Idee

Die sortierte Reihenfolge kann die Menge ersetzen. Fixiere nums[i], setze lo auf i+1 und hi auf den letzten Index und betrachte nums[i] + nums[lo] + nums[hi]. Bei einem Wert unter 0 brauchst du einen größeren Wert, also rückt lo nach rechts. Bei einem Wert über 0 brauchst du einen kleineren, also rückt hi nach links. Bei genau 0 speicherst du das Tripel und bewegst beide Zeiger.

Kein Tripel geht verloren. Ist die Summe kleiner als 0, reicht nums[lo] selbst mit dem größten noch verfügbaren Wert, nums[hi], nicht aus. Es kann sich also mit keinem Wert mehr im Bereich zu einem passenden Tripel ergänzen, und es zu verwerfen, geht nichts verloren. Bei einer Summe über 0 gilt das umgekehrte Argument: nums[hi] ist selbst mit dem kleinsten noch verfügbaren Wert zu groß. Jeder Schritt verwirft endgültig einen Wert. Daher braucht ein einzelnes i höchstens n Schritte und die gesamte Suche O(n²); abgesehen vom Sortieren und der Ausgabe wird kein zusätzlicher Speicher benötigt.

Betrachte die sortierte Liste [-2, -1, 0, 1, 1, 2]. Bei i = 0 (Wert -2) startet lo bei -1 und hi bei 2: Die Summe ist -1, also rückt lo auf 0. Jetzt ist -2 + 0 + 2 = 0, also speicherst du [-2, 0, 2], und beide Zeiger landen auf den beiden 1en, die [-2, 1, 1] ergeben. Bei i = 1 (Wert -1) ergibt 0 und 2 die Summe 1, also rückt hi zur zweiten 1, und -1 + 0 + 1 = 0 speichert [-1, 0, 1]. Beim Wert 0 an i = 2 wird nichts gefunden, und bei i = 3 ist der Wert positiv, also endet die Suche.

Für Wiederholungen brauchst du zwei Regeln. Überspringe ein i, dessen Wert dem vorherigen entspricht. Bewege nach einem Treffer lo über alle Kopien des verwendeten Werts hinweg. Für hi brauchst du keine eigene Regel: Wenn lo auf einem größeren Wert steht, ergibt eine Kopie des alten nums[hi] nun eine Summe über 0 und rückt dadurch von selbst weiter. Da i die unterschiedlichen Werte in aufsteigender Reihenfolge durchläuft und lo sich nur nach rechts bewegt, sind die Tripel sortiert.

Algorithmus

Sortiere nums.
Beende die Schleife für jedes i, wenn nums[i] > 0, und überspringe i, wenn nums[i] gleich nums[i-1] ist.
Setze lo = i+1 und hi = n-1. Addiere, solange lo < hi gilt, nums[i], nums[lo] und nums[hi].
Wenn die Summe kleiner als 0 ist, bewege lo nach rechts. Wenn sie größer als 0 ist, bewege hi nach links.
Wenn sie 0 ist, speichere das Tripel, bewege beide Zeiger und bewege dann lo an allen Kopien des verwendeten Werts vorbei.
Gib die Tripel zurück. Sie sind bereits sortiert.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen durch wiederholte Werte. Teste daher mit Eingaben, die solche Werte enthalten.

Wenn du i überspringst, wenn nums[i] gleich nums[i+1] ist, bleibt die letzte Kopie jedes Werts als erstes Element erhalten, und die Kopien davor sind verschwunden. In [-1, -1, 2] geht dadurch [-1, -1, 2] verloren. Vergleiche stattdessen mit der vorherigen Position, nums[i-1].
Wenn du bei nums[i] ≥ 0 statt bei nums[i] > 0 stoppst, übersiehst du [0, 0, 0].
Wiederholungen am Ende entfernen, statt sie zu überspringen. Bei 3000 Nullen zeichnet die Zwei-Zeiger-Schleife Millionen Kopien von [0, 0, 0] auf, bevor irgendeine Bereinigung stattfindet. Außerdem vergleicht ein Set aus Listen in mehreren Sprachen die Listen anhand ihrer Identität, sodass die Kopien ohnehin erhalten bleiben.
Dieselbe Position zweimal verwenden. Eine Hash-Set-Version, die das Set vorab mit der gesamten Liste füllt, macht aus [-2, 1, 3] [-2, 1, 1], indem sie die einzelne 1 zweimal verwendet. Suche nur nach Werten an Positionen, die du bereits durchlaufen hast.
Die Tripel unsortiert zurückgeben. Der Vergleich erfolgt exakt, daher muss die Hash-Set-Version jede Gruppe umkehren, und eine Lösung, die Tripel in einem Set sammelt, muss sie am Ende sortieren.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von 3Sum?

Die Lösung mit Sortieren und zwei Zeigern benötigt O(n²) Zeit. Das Sortieren kostet O(n log n), und jede der n Möglichkeiten für den ersten Wert erfordert einen Durchlauf mit O(n). Abgesehen vom Sortieren und der Ausgabe benötigt sie O(1) zusätzlichen Speicherplatz. Jedes Tripel zu überprüfen, benötigt stattdessen O(n³).

Wie vermeidet 3Sum doppelte Tripel?

Es sortiert die Liste, sodass gleiche Werte nebeneinander stehen. Dann überspringt es einen ersten Wert, der mit dem vorherigen übereinstimmt, und nach jedem Treffer bewegt es den linken Zeiger über alle Kopien des verwendeten Werts hinaus. Jedes Tripel wird genau einmal gefunden, anhand der ersten Vorkommen seiner Werte, sodass keine Ergebnismenge benötigt wird.

Sollte ich für 3Sum zwei Zeiger oder eine Hash-Menge verwenden?

Beide laufen in O(n²) Zeit. Zwei Zeiger benötigen keinen zusätzlichen Speicher, und die sortierte Reihenfolge liefert die Tripel bereits in der richtigen Reihenfolge. Eine Hash-Menge benötigt O(n) Speicher und erfordert Sorgfalt, damit die Positionen verschieden bleiben und die Ausgabe sortiert ist. Die Idee mit der Hash-Menge ist wichtig, wenn du nicht sortieren kannst, wie bei Two Sum, wo du die ursprünglichen Indizes zurückgibst.

Kann 3Sum schneller als in O(n²) gelöst werden?

Nicht viel. Die besten bekannten Algorithmen schlagen n² nur um einige logarithmische Faktoren, und viele Härteresultate in der algorithmischen Geometrie setzen voraus, dass kein Algorithmus eine Potenz von n unter 2 erreicht. Diese schnelleren Algorithmen sind Forschungsergebnisse, daher ist O(n²) die Antwort, die in Vorstellungsgesprächen erwartet wird.

Python

def threeSum(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

nums = [-2, 0, 1, 1, -1, 2]

Erwartet

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Probiere jedes Tripel aus

Fixiere einen Wert, finde das Paar mit einer Hashtabelle

Sortieren und zwei Zeiger verwenden

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben