. Kürzestes Subarray mit einer Summe von mindestens K

862. Kürzestes Subarray mit einer Summe von mindestens K

Schwierigkeit:Schwer

Themen: Array, Binäre Suche, Warteschlange, Schiebefenster, Heap (Prioritätswarteschlange), Präfixsumme, Monotone Warteschlange

Angenommen ein ganzzahliges Array nums und eine ganze Zahl k, geben Sie die Länge des kürzesten nichtleeren Unterarrays von nums mit einer Summe von mindestens k zurück. Wenn es kein solches Subarray gibt, geben Sie -1 zurück.

Ein Subarray ist ein zusammenhängender Teil eines Arrays.

Beispiel 1:

• Eingabe: nums = [1], k = 1
• Ausgabe: 1

Beispiel 2:

• Eingabe: nums = [1,2], k = 4
• Ausgabe: -1

Beispiel 3:

• Eingabe: nums = [2,-1,2], k = 3
• Ausgabe: 3

Einschränkungen:

• 1 5
• -10⁵ 5
• 1 9

Lösung:

Wir müssen einen Schiebefenster-Ansatz in Kombination mit Präfixsummen und einer monotonen Warteschlange verwenden. Hier ist die Schritt-für-Schritt-Anleitung:

Schritte:

1. Präfixsumme:

   • Berechnen Sie zunächst das Präfix-Summen-Array, wobei jedes Element am Index i die Summe der Elemente vom Anfang des Arrays bis i darstellt. Mit der Präfixsumme können wir die Summe eines beliebigen Subarrays in konstanter Zeit berechnen.

2. Monotonische Warteschlange:

   • Wir verwenden eine Deque (doppelendige Warteschlange), um die Indizes des prefix_sum-Arrays zu verwalten. Die Deque wird in aufsteigender Reihenfolge der Präfixsummen verwaltet.
   • Dies hilft uns, effizient Subarrays zu finden, deren Summe größer oder gleich k ist, indem wir die aktuelle Präfixsumme mit früheren Präfixsummen vergleichen.

3. Schiebefensterlogik:

   • Überprüfen Sie für jeden Index i, ob die Differenz zwischen der aktuellen Präfixsumme und einer vorherigen Präfixsumme (die in der Deque gespeichert ist) größer oder gleich k ist.
   • Wenn ja, berechnen Sie die Länge des Subarrays und aktualisieren Sie gegebenenfalls die Mindestlänge.

Algorithmus:

1. Prefix_sum-Array mit Größe n 1 initialisieren (wobei n die Länge des Eingabearrays ist). Das erste Element ist 0, da die Summe der Nullelemente 0 ist.
2. Verwenden Sie eine Deque, um Indizes von prefix_sum-Werten zu speichern. Die Deque hilft dabei, das kürzeste Subarray zu finden, das die Bedingung effizient erfüllt.
3. Aktualisieren Sie für jedes Element im Array die Präfixsumme und überprüfen Sie die Deque, um das kleinste Unterarray mit einer Summe größer oder gleich k zu finden.

Lassen Sie uns diese Lösung in PHP implementieren: 862. Kürzestes Subarray mit einer Summe von mindestens K

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function shortestSubarray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

Erläuterung:

1. Präfix-Summen-Array:

   • Wir berechnen die kumulative Summe des Arrays im Array prefix_sum. Dies hilft bei der Berechnung der Summe aller Subarrays nums[i...j] mithilfe der Formel prefix_sum[j 1] - prefix_sum[i].

2. Monotonische Warteschlange:

   • Die Deque enthält Indizes des prefix_sum-Arrays in aufsteigender Reihenfolge der Werte. Wir behalten diese Reihenfolge bei, damit wir effizient das kleinste Subarray finden können, dessen Summe größer oder gleich k ist.

3. Schiebefensterlogik:

   • Während wir das prefix_sum-Array durchlaufen, versuchen wir, das kleinste Subarray zu finden, indem wir die Differenz zwischen dem aktuellen prefix_sum[i] und dem vorherigen prefix_sum[deque[0]] verwenden.
   • Wenn die Differenz größer oder gleich k ist, berechnen wir die Subarray-Länge und aktualisieren die gefundene Mindestlänge.

4. Zurückgegebenes Ergebnis:

   • Wenn kein gültiges Subarray gefunden wird, geben Sie -1 zurück. Andernfalls wird die minimale Subarray-Länge zurückgegeben.

Zeitkomplexität:

• Zeitkomplexität: O(n), wobei n die Länge des Eingabearrays ist. Jedes Element wird höchstens zweimal verarbeitet (einmal beim Hinzufügen zur Deque und einmal beim Entfernen).
• Raumkomplexität: O(n) aufgrund des prefix_sum-Arrays und der zum Speichern von Indizes verwendeten Deque.

Dieser Ansatz stellt sicher, dass die Lösung auch bei großen Eingaben effizient läuft.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Kürzestes Subarray mit einer Summe von mindestens K. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!