Maximale Summe unterschiedlicher Subarrays mit der Länge K

2461. Maximale Summe unterschiedlicher Subarrays mit der Länge K

Schwierigkeit:Mittel

Themen:Array, Hash-Tabelle, Schiebefenster

Sie erhalten ein ganzzahliges Array nums und eine ganze Zahl k. Finden Sie die maximale Subarray-Summe aller Subarrays von Zahlen, die die folgenden Bedingungen erfüllen:

• Die Länge des Subarrays beträgt k und
• Alle Elemente des Subarrays sind unterscheidbar.

Gib die maximale Subarray-Summe aller Subarrays zurück, die die Bedingungen erfüllen. Wenn kein Unterarray die Bedingungen erfüllt, geben Sie 0 zurück.

Ein Subarray ist eine zusammenhängende, nicht leere Folge von Elementen innerhalb eines Arrays.

Beispiel 1:

• Eingabe: nums = [1,5,4,2,9,9,9], k = 3
• Ausgabe: 15
• Erklärung: Die Subarrays von Nums mit der Länge 3 sind:
  • [1,5,4], das die Anforderungen erfüllt und eine Summe von 10 hat.
  • [5,4,2], das die Anforderungen erfüllt und eine Summe von 11 hat.
  • [4,2,9] was die Anforderungen erfüllt und eine Summe von 15 hat.
  • [2,9,9] was die Anforderungen nicht erfüllt, da das Element 9 wiederholt wird.
  • [9,9,9] was die Anforderungen nicht erfüllt, da das Element 9 wiederholt wird.
  • Wir geben 15 zurück, weil es die maximale Subarray-Summe aller Subarrays ist, die die Bedingungen erfüllen

Beispiel 2:

• Eingabe: nums = [4,4,4], k = 3
• Ausgabe: 0
• Erklärung: Die Subarrays von Nums mit der Länge 3 sind:
  • [4,4,4] was die Anforderungen nicht erfüllt, da das Element 4 wiederholt wird.
  • Wir geben 0 zurück, da keine Subarrays die Bedingungen erfüllen.

Einschränkungen:

• 1 <= k <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵

Hinweis:

1. Welche Elemente ändern sich, wenn man vom Subarray der Größe k, das bei Index i endet, zum Subarray der Größe k wechselt, das bei Index i 1 endet?
2. Nur ​​zwei Elemente ändern sich, das Element bei i 1 wird zum Subarray hinzugefügt und das Element bei i - k 1 wird aus dem Subarray entfernt.
3. Durchlaufen Sie jedes Subarray der Größe k und behalten Sie die Summe des Subarrays und die Häufigkeit jedes Elements im Auge.

Lösung:

Wir können diesen Schritten folgen:

Ansatz:

1. Schiebefenster: Die Fenstergröße beträgt k, und wir schieben das Fenster durch das Array, während wir die Summe des aktuellen Fensters beibehalten und prüfen, ob alle Elemente im Fenster unterschiedlich sind.
2. Hash-Tabelle (oder assoziatives Array): Verwenden Sie ein assoziatives Array (Hash-Tabelle), um die Häufigkeit von Elementen im aktuellen Fenster zu verfolgen. Wenn ein Element mehr als einmal vorkommt, ist das Fenster ungültig.
3. Aktualisierung des Fensters: Während wir das Fenster verschieben, fügen wir das neue Element hinzu (d. h. das Element, das in das Fenster kommt) und entfernen das alte Element (d. h. das Element, das das Fenster verlässt). Aktualisieren Sie die Summe entsprechend und prüfen Sie, ob das Fenster gültig ist (d. h. alle Elemente eindeutig sind).
4. Die maximale Summe zurückgeben: Wir müssen die maximale Summe verfolgen, die zwischen gültigen Subarrays auftritt.

Algorithmus:

1. Initialisieren Sie eine Hash-Tabellenhäufigkeit, um die Häufigkeit von Elementen im aktuellen Fenster zu speichern.
2. Berechnen Sie zunächst die Summe für das erste Fenster der Größe k und speichern Sie das Ergebnis, wenn das Fenster unterschiedliche Elemente enthält.
3. Schieben Sie das Fenster von links nach rechts um:
   • Entfernen des Elements, das das Fenster von links verlässt.
   • Hinzufügen des Elements, das von rechts in das Fenster eintritt.
   • Aktualisieren Sie die Summe und die Hash-Tabelle und prüfen Sie, ob das Fenster immer noch nur eindeutige Elemente enthält.
4. Wenn das Fenster gültige unterschiedliche Elemente enthält, aktualisieren Sie die maximale Summe.
5. Wenn kein gültiges Subarray gefunden wird, geben Sie 0 zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2461. Maximale Summe unterschiedlicher Subarrays mit der Länge K

  
  
  Erläuterung:




Variablen:



$maxSum: Verfolgt die maximale Summe eines bisher gefundenen gültigen Subarrays.

$currentSum: Enthält die Summe des aktuellen Schiebefensters der Größe k.

$freq: Eine Hash-Tabelle (oder ein assoziatives Array), die die Häufigkeit von Elementen im aktuellen Fenster speichert.



Schiebefenster:


Wir durchlaufen das Array mit einer Schleife. Wenn wir das Fenster verschieben, geschieht Folgendes:


Fügen Sie das Element am Index $i zur Summe hinzu und aktualisieren Sie seine Häufigkeit.
Wenn die Fenstergröße k überschreitet, entfernen wir das Element am Index $i - k aus der Summe und reduzieren seine Häufigkeit.





Prüfung gültiger Fenster:


Sobald die Fenstergröße k erreicht (d. h. wenn $i >= k - 1), prüfen wir, ob alle Elemente im Fenster unterschiedlich sind, indem wir sicherstellen, dass die Anzahl der unterschiedlichen Schlüssel in der Häufigkeitskarte gleich k ist. Wenn ja, aktualisieren wir die Höchstsumme.



Ergebnis zurückgeben:

Nachdem wir das Array durchlaufen haben, geben wir die maximal gefundene Summe zurück. Wenn kein gültiges Subarray gefunden wurde, bleibt maxSum 0.





  
  
  Zeitkomplexität:




O(n), wobei n die Länge des Nums-Arrays ist. Jedes Element wird einmal zum Schiebefenster hinzugefügt und daraus entfernt, und die Hash-Tabellenoperationen (Einfügen, Entfernen, Anzahl prüfen) sind im Durchschnitt O(1).



  
  
  Raumkomplexität:




O(k) für die Hash-Tabelle, die die Häufigkeit von Elementen im aktuellen Fenster speichert.


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 vonMaximale Summe unterschiedlicher Subarrays mit der Länge K. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!