4Sum

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

O(n³). Die beiden Schleifen wählen etwa n²/2 Paare (i, j) aus, und für jedes davon wird ein Durchlauf mit zwei Zeigern mit höchstens n Schritten ausgeführt; die Sortierung in O(n log n) ist im Vergleich dazu vernachlässigbar.

Q: Wie verallgemeinerst du 4Sum zu kSum?

Schreibe kSum(nums, target, k) für eine sortierte Liste. Für k = 2 wird der Zwei-Zeiger-Durchlauf ausgeführt. Bei einem größeren k durchläuft die Funktion den ersten Wert, überspringt Wiederholungen und ruft sich selbst mit k-1 und target - nums[i] für die Werte rechts davon auf. Jede Ebene fügt einen Faktor n hinzu, daher hat kSum die Laufzeit O(n^(k-1)).

Q: Kann 4Sum in O(n²) gelöst werden?

Du kannst die n²/2 Paarsummen in einer Hash-Map gruppieren und jedes Paar mit Paaren abgleichen, deren Summe target minus seiner eigenen Summe ist. Das ist schnell, wenn nur wenige Paare dieselbe Summe haben, aber eine Summe kann O(n²) Paare enthalten, sodass der schlechteste Fall nicht besser als O(n³) ist.

MittelZwei Zeiger Sortieren

+10

Du erhältst eine Liste von Ganzzahlen nums und eine Ganzzahl target. Gib jedes Vierertupel [a, b, c, d] zurück, dessen vier Werte an vier verschiedenen Positionen in nums stehen und zusammen target ergeben. Gib jedes Vierertupel mit seinen Werten in nicht absteigender Reihenfolge an. Wenn sich dieselben vier Werte an verschiedenen Positionen auswählen lassen, erscheint das Vierertupel trotzdem nur einmal. Sortiere die Antwort zuerst nach dem ersten Wert, dann nach dem zweiten und schließlich nach dem dritten. Wenn kein Vierertupel passt, gib eine leere Liste zurück.

Funktion

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: die Zahlen, aus denen man auswählen kann, mindestens eine
targetinteger: die Summe, die jedes Vierertupel erreichen muss
Gibt zurückinteger-2d-array: die eindeutigen Vierergruppen mit Summe target, jede davon sortiert und auch die Liste sortiert; eine leere Liste, falls es keine gibt

Einschränkungen

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
Die Summe beliebiger vier Werte liegt zwischen -4 × 10⁸ und 4 × 10⁸ und passt daher in eine 32-Bit-Ganzzahl.
Vierlinge, die dieselben vier Werte enthalten, zählen als einer.

Beispiele

Eingabe: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Ausgabe: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Erklärung: Jedes der vier Vierergruppen ergibt in der Summe 1, zum Beispiel -3 + (-1) + 2 + 3. Die beiden, die mit -3 beginnen, kommen zuerst und sind nach ihrem zweiten Wert geordnet: -1 vor 0.

Eingabe: nums = [4, 4, 4, 4, 4, 4]target = 16
Ausgabe: [[4, 4, 4, 4]]
Erklärung: Alle 15 Möglichkeiten, vier Positionen aus sechs auszuwählen, ergeben vier 4er, die zusammen 16 ergeben. Daher kommt [4, 4, 4, 4] einmal vor.

Eingabe: nums = [1, 5, 2, 9]target = 3
Ausgabe: []
Erklärung: Die einzige Möglichkeit sind alle vier Zahlen, und 1 + 5 + 2 + 9 = 17, nicht 3, also ist die Antwort eine leere Liste.

Weiterführende Frage

Zähle die Mengen aus vier Positionen, deren Werte zusammen target ergeben, und nicht die unterschiedlichen Vierergruppen. Das zweite Beispiel hat 15. Schaffst du das in O(n²)?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Vierergruppe von Positionen zu überprüfen kostet O(n⁴), und wiederholte Werte erzeugen dasselbe Vierertupel viele Male. Wende die 3Sum-Reduktion eine Ebene tiefer an: Sortiere, fixiere die ersten beiden Werte mit zwei Schleifen, finde das letzte Paar mit zwei Zeigern und überspringe auf jeder Ebene wiederholte Werte.

Probiere jede Viererkombination aus

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

Idee

Sortiere zuerst, damit die Positionen i < j < k < l Werte in nicht absteigender Reihenfolge enthalten und jedes Vierertupel in der richtigen Reihenfolge ausgegeben wird. Vier verschachtelte Schleifen erreichen jede Auswahl von vier Positionen. Um Wiederholungen zu vermeiden, fährt eine Schleife fort, wenn die nächste Position den Wert enthält, den sie einen Schritt zuvor ausprobiert hat. Bei sechs 4ern probiert jede Schleife nur ihre erste Position aus, sodass [4, 4, 4, 4] einmal statt 15-mal ausgegeben wird.

Bei 200 Zahlen gibt es 64,684,950 Vierermengen, und die Anzahl wächst etwa um den Faktor 16, wenn sich n verdoppelt.

Algorithmus

Sortiere nums.
Verschachtele vier Schleifen über i < j < k < l, wobei jede eine Position hinter der sie umgebenden Schleife beginnt.
Überspringe in jeder Schleife eine Position, die nicht die erste der Schleife ist und denselben Wert wie die vorherige Position enthält.
Speichere [nums[i], nums[j], nums[k], nums[l]], wenn die vier Werte zusammen target ergeben. Die Schleifen liefern sie in sortierter Reihenfolge.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Sortieren, zwei Schleifen, zwei Zeiger

Idee

Fixiere nums[i] und nums[j]; übrig bleibt eine Frage nach einem Paar: Finde zwei Werte rechts von j, deren Summe target - nums[i] - nums[j] ergibt. Bei einer sortierten Liste genügt ein Durchlauf. Setze lo auf j+1 und hi auf den letzten Index. Ist die Summe kleiner als target, bewege lo nach rechts; ist sie größer, bewege hi nach links.

Bei jedem Schritt wird ein Wert ausgeschlossen, der zu keiner Lösung gehört. Ist die Summe zu klein, reicht selbst der größte verbleibende Wert, nums[hi], zusammen mit nums[lo] nicht aus, also kann nums[lo] ausgeschlossen werden. Ist die Summe zu groß, wird aus demselben Grund nums[hi] ausgeschlossen. Für ein Paar (i, j) sind höchstens n Schritte nötig, also kosten die n²/2 Paare O(n³).

Im ersten Beispiel bewegt sich lo bei i auf -3 und j auf -1 von 0 über 1 bis 2, wo -3 + (-1) + 2 + 3 = 1 gilt.

Algorithmus

Sortiere nums.
Überspringe jedes i, wenn i > 0 gilt und nums[i] gleich nums[i-1] ist.
Überspringe jedes j nach i, wenn j > i+1 gilt und nums[j] gleich nums[j-1] ist.
Setze lo = j+1 und hi = n-1. Vergleiche, solange lo < hi gilt, die Summe der vier Werte mit target: Ist sie kleiner, bewege lo nach rechts; ist sie größer, bewege hi nach links.
Speichere bei einer Übereinstimmung das Quadrupel, bewege beide Zeiger und erhöhe anschließend lo, solange es den zuvor verwendeten Wert enthält.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

Stolperfallen und Grenzfälle

j überspringen, wenn nums[j] gleich nums[j-1] ist. Bei j = i+1 wird mit dem Wert verglichen, den i verwendet. Dadurch geht bei [2, 2, 2, 2, 2] mit dem Zielwert 8 [2, 2, 2, 2] verloren.
Den vorzeitigen Abbruch von 3Sum nums[i] > target übernehmen. Bei [-5, -4, -3, -2, -1] und dem Zielwert -10 stoppt die Schleife bei -5 und übersieht [-4, -3, -2, -1].
Listen mit weniger als vier Elementen. Bei einer oder zwei Zahlen ist n-3 negativ: 0..<(n - 3) führt in Swift zu einer Panik, und n - 3 läuft bei einem Rust-usize unter. Gib zuerst eine leere Liste zurück.
Quartette in einem Hash-Set sammeln und unsortiert zurückgeben.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von 4Sum?

O(n³). Die beiden Schleifen wählen etwa n²/2 Paare (i, j) aus, und für jedes davon wird ein Durchlauf mit zwei Zeigern mit höchstens n Schritten ausgeführt; die Sortierung in O(n log n) ist im Vergleich dazu vernachlässigbar.

Wie verallgemeinerst du 4Sum zu kSum?

Schreibe kSum(nums, target, k) für eine sortierte Liste. Für k = 2 wird der Zwei-Zeiger-Durchlauf ausgeführt. Bei einem größeren k durchläuft die Funktion den ersten Wert, überspringt Wiederholungen und ruft sich selbst mit k-1 und target - nums[i] für die Werte rechts davon auf. Jede Ebene fügt einen Faktor n hinzu, daher hat kSum die Laufzeit O(n^(k-1)).

Kann 4Sum in O(n²) gelöst werden?

Du kannst die n²/2 Paarsummen in einer Hash-Map gruppieren und jedes Paar mit Paaren abgleichen, deren Summe target minus seiner eigenen Summe ist. Das ist schnell, wenn nur wenige Paare dieselbe Summe haben, aber eine Summe kann O(n²) Paare enthalten, sodass der schlechteste Fall nicht besser als O(n³) ist.

def fourSum(nums, target):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe

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