Longest Subarray with Sum K

+10

Gegeben sind die Ganzzahlen nums und ein Zielwert k. Gib die Länge des längsten Teilarrays zurück, dessen Elemente zusammen genau k ergeben. Ein Teilarray ist eine Folge aufeinanderfolgender Elemente mit einer Länge von mindestens eins. Einige Werte können null oder kleiner als null sein. Wenn die Summe eines Teilarrays nicht k ergibt, gib 0 zurück.

Funktion

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: die zu durchsuchenden Ganzzahlen, einschließlich negativer Zahlen und Nullen
kinteger: die genaue Summe, die das Teilarray haben muss
Gibt zurückinteger: die Länge des längsten Teilarrays, dessen Summe k ergibt, oder 0, wenn es keines gibt

Einschränkungen

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Jede Präfixsumme liegt zwischen -2 × 10⁸ und 2 × 10⁸, daher reichen 32-Bit-Ganzzahlen aus.
Gib 0 zurück, wenn kein Teilarray die Summe k ergibt.

Beispiele

Eingabe: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Ausgabe: 5
Erklärung: Drei Läufe ergeben zusammen 5: [2, 3] am Ende, [2, -1, 3, 1] am Anfang und [3, 1, -4, 2, 3] an den Indizes 2 bis 6. Der letzte ist mit 5 Elementen der längste.

Eingabe: nums = [4, 1, 1, 2, -1, 1]k = 3
Ausgabe: 4
Erklärung: [1, 1, 2, -1] an den Indizes 1 bis 4 und [1, 2, -1, 1] an den Indizes 2 bis 5 ergeben beide mit 4 Elementen zusammen 3. Du gibst eine Länge zurück, daher spielt der Gleichstand keine Rolle.

Weiterführende Frage

Wie würdest du das längste Teilarray finden, dessen Summe höchstens k beträgt, wobei negative Werte weiterhin erlaubt sind?

Tipps

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

0 von 3 geöffnet

Lösung

Laufende Summen verwandeln die Summe eines beliebigen Teilarrays in eine einzige Subtraktion: Die Elemente nach Index s bis einschließlich Index i ergeben zusammen prefix[i] - prefix[s]. Merke dir den ersten Index, an dem jede Summe auftritt, und ein einziger Durchlauf findet die längste Übereinstimmung, die an jeder Position endet.

Erweitere jedes Teilarray von jedem Startpunkt aus

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

Idee

Erweitere von jedem Start aus nach rechts und addiere jedes Element zu einer laufenden Summe. Sobald die Summe k entspricht, notiere die Länge. Jedes Teilarray ist ein Paar aus Start- und Endindex, sodass keines übersehen wird. Erweitere weiter, nachdem die Summe k überschritten hat: Ab Index 2 sind die Summen im ersten Beispiel 3, 4, 0, 2, 5, und wegen der -4 erreicht die letzte den Wert 5.

Es gibt etwa n²/2 Paare: 2 × 10^8 Additionen für n = 2 × 10^4.

Algorithmus

Setze best auf 0.
Setze für jedes start total auf 0.
Bewege end von start bis zum letzten Index und addiere nums[end] zu total.
Wenn total gleich k ist, setze best auf den größeren Wert von best und end - start + 1.
Gib best zurück.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Präfixsummen mit dem ersten Index jeder Summe

Idee

Ein Lauf, der bei Index i endet, ergibt genau dann die Summe k, wenn eine frühere Summe gleich prefix - k ist. Wenn mehrere frühere Summen infrage kommen, beginnt die erste davon den längsten Lauf; deshalb speichert die Map jede Summe nur bei ihrem ersten Auftreten. Eine spätere Wiederholung könnte nur einen kürzeren Lauf beginnen. Initialisiere die Map mit der Summe 0 bei Index -1, damit ein Treffer, der bei Index 0 beginnt, die Länge i + 1 erhält.

Im ersten Beispiel lauten die Summen 2, 1, 4, 5, 1, 3, 6. Bei Index 6 ist 6 - 5 = 1 erstmals bei Index 1 aufgetreten, was die Länge 5 ergibt. Die Summe 1 tritt bei Index 4 erneut auf, und wenn Index 1 gespeichert bleibt, wird genau dieser Lauf gefunden.

Eine Abfrage pro Element ergibt eine Laufzeit von O(n), und die Map enthält höchstens n + 1 Summen.

Algorithmus

Erstelle eine Map first, die bei Index -1 den Gesamtwert 0 enthält, und setze prefix und best auf 0.
Addiere für jeden Index i nums[i] zu prefix.
Falls prefix - k in der Map am Index start steht, setze best auf den größeren Wert von best und i - start.
Falls prefix noch nicht in der Map steht, speichere es mit dem Index i.
Gib best zurück.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Stolperfallen und Grenzfälle

Wenn bei jeder Wiederholung einer Summe der gespeicherte Index überschrieben wird, bleibt der neueste Start erhalten und es wird eine kürzere Übereinstimmung gefunden. Das erste Beispiel gibt 4 statt 5 zurück, weil die Summe 1 von Index 1 zu Index 4 wandert.
Ein Fenster, das verkleinert wird, solange seine Summe größer als k ist, gibt im ersten Beispiel ebenfalls 4 zurück. Es endet mit [-1, 3, 1, -4, 2, 3] und einer Summe von 4 und entfernt nie die -1.
Wenn die Summe 0 bei Index -1 weggelassen wird, werden alle Übereinstimmungen verpasst, die bei Index 0 beginnen: [5, 0, 0, 0] mit k = 5 gibt 0 statt 4 zurück.
Der gespeicherte Index ist die Position vor dem Teilarray, daher ist die Länge i - start. Wenn 1 addiert wird, wird ein Element zu viel gezählt.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität des längsten Teilarrays mit der Summe K?

O(n) Zeit und O(n) zusätzlicher Speicherplatz mit laufenden Summen und einer Map der ersten Indizes: ein Nachschlagen und höchstens ein Einfügen pro Element. Jedes Teilarray von jedem Startpunkt aus zu erweitern, kostet O(n²) Zeit und O(1) Speicherplatz.

Warum funktioniert ein Sliding Window nicht, wenn das Array negative Zahlen enthält?

Ein gleitendes Fenster geht davon aus, dass das Hinzufügen eines Elements die Summe erhöht und das Entfernen eines Elements sie verringert. Bei negativen Werten kann ein Fenster, dessen Summe zu groß ist, k trotzdem erreichen, sobald ein negatives Element hinzukommt, und bei einem Fenster, dessen Summe zu klein ist, muss möglicherweise links ein negatives Element entfernt werden. Das Fenster kann nicht erkennen, welcher Schritt der richtige ist.

Lässt sich das längste Teilarray mit Summe K mit O(1) zusätzlichem Speicher lösen?

Nur wenn kein Wert negativ ist. Dann sinkt die Summe nie, wenn das Fenster größer wird, und zwei Zeiger finden in O(n) Zeit und mit O(1) Speicher das längste Fenster mit der Summe k. Bei negativen Werten brauchst du die Map der Summen oder die O(n²)-Suche.

def longestSubarrayWithSumK(nums, k):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Erwartete Ausgabe