Minimum Size Subarray Sum

Q: Wie hoch ist die Zeitkomplexität von „Minimum Size Subarray Sum“?

Die Lösung mit dem gleitenden Fenster benötigt O(n) Zeit und O(1) Speicherplatz. Die innere Schleife sieht so aus, als könnte sie eine quadratische Laufzeit verursachen, aber left bewegt sich nur vorwärts und wird daher während des gesamten Durchlaufs höchstens n -mal erhöht. Die Version mit Präfixsummen benötigt O(n log n) , und jede Startposition zu überprüfen benötigt O(n²) .

Q: Warum die Präfixsummenlösung mit O(n log n) lernen, wenn es O(n) gibt?

Interviewer fragen oft danach, nachdem du die Antwort O(n) gegeben hast. Es zeigt eine zweite Verwendung positiver Werte: Die Präfixsummen sind sortiert, sodass eine binäre Suche findet, wo eine laufende Summe erstmals einen Schwellenwert überschreitet. Dieses Werkzeug kommt in anderen Problemen wieder zum Einsatz, etwa wenn ein Index zufällig proportional zu seinem Gewicht ausgewählt werden soll.

Q: Muss die Summe des Teilarrays genau dem Zielwert entsprechen?

Nein. Jede Summe, die größer oder gleich target ist, zählt. Bei target = 15 ergibt das Fenster 9, 3, 7 eine Summe von 19 und hat weiterhin die Länge 3. Wenn du stattdessen eine exakte Summe benötigst, funktioniert das Fenster bei positiven Werten weiterhin: Verkleinere es, solange die Summe über dem Zielwert liegt, und erfasse eine Länge nur, wenn die Summe gleich dem Zielwert ist.

MittelSliding Window Präfixsummen

+10

Du erhältst eine positive Ganzzahl target und ein Array nums aus positiven Ganzzahlen. Finde das kürzeste Teilarray (eine Folge benachbarter Elemente), dessen Summe mindestens target beträgt, und gib seine Länge zurück. Wenn kein Teilarray target erreicht, gib 0 zurück.

Funktion

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: die Summe, die ein Teilarray erreichen oder überschreiten muss
numsinteger-array: das Array positiver Ganzzahlen
Gibt zurückinteger: die Länge des kürzesten Teilarrays mit einer Summe von mindestens target oder 0, falls keines existiert

Einschränkungen

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Beispiele

Eingabe: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Ausgabe: 3
Erklärung: Keine zwei benachbarten Zahlen erreichen 15: Das größte Paar ist 9 + 3 = 12. Drei erreichen es: 4 + 2 + 9 = 15 und 9 + 3 + 7 = 19, also lautet die Antwort 3.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Wie würdest du das lösen, wenn nums auch Nullen und negative Zahlen enthalten könnte, sodass das gleitende Fenster nicht mehr funktioniert?

Tipps

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

0 von 3 geöffnet

Lösung

Die Werte sind alle positiv, daher erhöht das Verlängern eines Teilarrays immer seine Summe und das Kürzen senkt sie immer. Diese eine Tatsache ermöglicht beide schnellen Lösungen. Präfixsummen bilden eine sortierte Liste, sodass eine binäre Suche die Stelle findet, an der eine Summe zum ersten Mal target erreicht. Noch besser: Das beste Ende bewegt sich nie nach links, wenn sich der Start nach rechts bewegt. Daher findet ein einzelnes Fenster, das sich rechts vergrößert und links verkleinert, die Antwort in einem Durchlauf.

Von jedem Startpunkt aus erweitern

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

Idee

Lege einen Startindex fest und addiere die Werte nacheinander nach rechts. Sobald die laufende Summe target erreicht, hast du das kürzeste Teilarray, das an diesem Start beginnt: Jedes kürzere Teilarray endete früher, und seine Summe war noch zu klein. Halte also seine Länge fest, erweitere das Teilarray nicht weiter und gehe zum nächsten Start. Die Antwort ist die kleinste Länge über alle Startpositionen hinweg.

Bei target = 15 und [4, 2, 9, 3, 7, 1, 5] ergeben sich ab Start 0 die Summen 4, 6, 15; das Teilarray endet also bei Länge 3. Ab Start 1 ergeben sich die Summen 2, 11, 14, 21; das Teilarray endet bei Länge 4. Ab Start 2 ergeben sich die Summen 9, 12, 19; Länge 3 also erneut. Kein Start ergibt eine kleinere Länge als 3.

Problematisch wird es, wenn der Zielwert schwer zu erreichen ist. Erreicht kein Teilarray den Zielwert, läuft jeder Start bis zum Ende des Arrays: n(n+1)/2 Additionen, also 2 × 10^8 bei n = 2 × 10^4. Außerdem berechnet jeder Start Summen erneut, die bereits beim vorherigen Start berechnet wurden.

Algorithmus

Setze best auf 0, das bedeutet, dass bisher nichts gefunden wurde.
Setze für jeden Startindex eine laufende Summe auf 0.
Bewege einen Endindex vom Start aus nach rechts und addiere nums[end] zur Summe.
Wenn die Summe target erreicht, behalte end-start+1, falls dieser Wert best übertrifft, und erweitere diesen Start nicht weiter.
Gib best zurück.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Präfixsummen und binäre Suche

Idee

Sei prefix[k] die Summe der ersten k Werte, wobei prefix[0] = 0 gilt. Die Summe von nums[start..end-1] ist dann prefix[end] - prefix[start]. Für einen festen Start suchst du das kleinste end mit prefix[end] ≥ prefix[start] + target.

Alle Werte sind positiv, also ist prefix streng monoton steigend, und die erste Position, an der ein Wert erreicht wird, lässt sich per binärer Suche finden. Für [4, 2, 9, 3, 7, 1, 5] ist prefix gleich [0, 4, 6, 15, 18, 25, 26, 31]. Ab Start 2 benötigst du 6 + 15 = 21; der erste Präfixwert, der mindestens 21 beträgt, ist 25 an Index 5, also ist das Fenster nums[2..4] = 9, 3, 7 und hat die Länge 3.

Wenn sogar prefix[n] kleiner ist als der benötigte Wert für einen Start, funktioniert kein end dafür, und auch für keinen späteren Start, da prefix[start] nur wächst. Beende die Suche an dieser Stelle. Das sind n binäre Suchen, also eine Laufzeit von O(n log n), zuzüglich O(n) für das Präfixarray. Der größte verglichene Wert ist 2 × 10^8 + 10^9 und passt in eine 32-Bit-Ganzzahl.

Algorithmus

Erstelle ein prefix der Länge n+1 mit prefix[k+1] = prefix[k] + nums[k].
Berechne für jeden Start need = prefix[start] + target.
Wenn prefix[n] < need gilt, brich ab: Kein späterer Start kann erfolgreich sein.
Führe für die Positionen start+1 bis n eine binäre Suche nach dem ersten end mit prefix[end] ≥ need durch und berücksichtige end-start, wenn es bisher die kürzeste Länge ist.
Gib die kürzeste Länge zurück oder 0, wenn kein Start erfolgreich war.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Gleitendes Fenster

Idee

Behalte ein Fenster nums[left..right] und seine Summe bei. Verschiebe right Schritt für Schritt nach rechts und addiere den neuen Wert. Solange die Summe mindestens target beträgt, ist das Fenster ein Kandidat: Halte seine Länge fest, entferne dann nums[left] und verschiebe left nach vorn, um zu prüfen, ob ein kürzeres Fenster immer noch funktioniert.

Warum kann left endgültig entfernt werden? Wenn das Fenster nums[left..right] erstmals target erreicht, hat das kleinere Fenster nums[left..right-1] diesen Wert nicht erreicht, denn die Schleife hätte es im vorherigen Schritt verkleinert. Daher ist right das früheste Ende für diesen Start, und jedes spätere Ende ergibt nur ein längeres Teilarray. Für diesen Start wurde die bestmögliche Antwort gefunden. Diese Argumentation setzt positive Werte voraus: Bei einer negativen Zahl könnte ein längeres Fenster später eine größere Summe haben.

Bei target = 15 und [4, 2, 9, 3, 7, 1, 5]: Die Summe steigt auf 4, 6, 15, also wird Länge 3 festgehalten und 4 entfernt (11). Beim Addieren von 3 ergibt sich 14, beim Addieren von 7 ergibt sich 21: Länge 4 festhalten, 2 entfernen (19), Länge 3 festhalten, 9 entfernen (10). Beim Addieren von 1 und 5 ergibt sich 16: Länge 4 festhalten, 3 entfernen (13). Die Antwort ist 3.

Die while-Schleife befindet sich innerhalb der for-Schleife, doch jeder Index gelangt genau einmal in das Fenster und verlässt es genau einmal, sodass der Gesamtaufwand O(n) beträgt. Es werden nur drei Zahlen gespeichert, daher beträgt der Speicherbedarf O(1).

Algorithmus

Setze left = 0, total = 0 und best = 0.
Addiere für jedes right nums[right] zu total.
Solange total ≥ target gilt, behalte right-left+1, wenn es best übertrifft, ziehe nums[left] ab und bewege left um einen Schritt nach rechts.
Gib best zurück, das weiterhin 0 ist, wenn die Summe target nie erreicht hat.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Stolperfallen und Grenzfälle

Die meisten Fehler entstehen beim Verkleinern des Fensters und bei dem Wert, den du zurückgibst, wenn die Summe nie target erreicht.

Das Fenster mit if statt mit while verkleinern. Für target = 12 und [1, 1, 2, 3, 12] ergibt das Hinzufügen von 12 eine Summe von 19. Ein if speichert die Länge 5, entfernt einen Wert und macht weiter, sodass das Fenster [12] der Länge 1 nie gemessen wird. Eine Schleife entfernt weiterhin Werte, solange die Summe noch ausreicht.
Die Länge erst nach dem Entfernen von nums[left] speichern. Das gemessene Fenster muss dasjenige sein, dessen Summe target erreicht hat.
Mit > statt mit ≥ vergleichen. Ein Teilarray, dessen Summe target entspricht, zählt: Für [3, 3, 3] mit target = 9 ist die Antwort 3, nicht 0.
Den Sentinel zurückgeben. Wenn du best mit n+1 oder unendlich initialisierst, setze den Wert auf 0, wenn die Summe target nie erreicht hat.
Das Fenster bei Arrays mit Nullen oder negativen Zahlen wiederverwenden. Der Ansatz setzt voraus, dass jeder Wert positiv ist. Diese Aufgabe garantiert das, Varianten jedoch nicht.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von „Minimum Size Subarray Sum“?

Die Lösung mit dem gleitenden Fenster benötigt O(n) Zeit und O(1) Speicherplatz. Die innere Schleife sieht so aus, als könnte sie eine quadratische Laufzeit verursachen, aber left bewegt sich nur vorwärts und wird daher während des gesamten Durchlaufs höchstens n-mal erhöht. Die Version mit Präfixsummen benötigt O(n log n), und jede Startposition zu überprüfen benötigt O(n²).

Warum benötigt das gleitende Fenster positive Zahlen?

Wenn das Fenster verkleinert wird, muss seine Summe sinken, und wenn es vergrößert wird, muss sie steigen. Andernfalls könnte das Entfernen des linken Elements den Anfang der Antwort verwerfen. Bei negativen Zahlen funktioniert diese Reihenfolge nicht. Die übliche Lösung sind Präfixsummen mit einer monotonen Deque möglicher Startpositionen, die weiterhin in O(n) läuft.

Warum die Präfixsummenlösung mit O(n log n) lernen, wenn es O(n) gibt?

Interviewer fragen oft danach, nachdem du die Antwort O(n) gegeben hast. Es zeigt eine zweite Verwendung positiver Werte: Die Präfixsummen sind sortiert, sodass eine binäre Suche findet, wo eine laufende Summe erstmals einen Schwellenwert überschreitet. Dieses Werkzeug kommt in anderen Problemen wieder zum Einsatz, etwa wenn ein Index zufällig proportional zu seinem Gewicht ausgewählt werden soll.

Muss die Summe des Teilarrays genau dem Zielwert entsprechen?

Nein. Jede Summe, die größer oder gleich target ist, zählt. Bei target = 15 ergibt das Fenster 9, 3, 7 eine Summe von 19 und hat weiterhin die Länge 3. Wenn du stattdessen eine exakte Summe benötigst, funktioniert das Fenster bei positiven Werten weiterhin: Verkleinere es, solange die Summe über dem Zielwert liegt, und erfasse eine Länge nur, wenn die Summe gleich dem Zielwert ist.

Python

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

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Erwartet

Minimum Size Subarray Sum

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Von jedem Startpunkt aus erweitern

Präfixsummen und binäre Suche

Gleitendes Fenster

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben