Anzahl der Möglichkeiten, das Array aufzuteilen

2270. Anzahl der Möglichkeiten, das Array aufzuteilen

Schwierigkeit:Mittel

Themen:Array, Präfixsumme

Sie erhalten ein 0-indiziertes ganzzahliges Array mit Zahlen der Länge n.

nums enthält eine gültige Aufteilung am Index i, wenn Folgendes zutrifft:

• Die Summe der ersten i 1 Elemente ist größer oder gleichdie Summe der letzten n - i - 1 Elemente.
• Es gibt mindestens ein Element rechts von i. Das heißt, 0 <= i < n - 1.

Gib die Anzahl der gültigen Teilungen in Zahlen zurück.

Beispiel 1:

• Eingabe: nums = [10,4,-8,7]
• Ausgabe: 2
• Erklärung: Es gibt drei Möglichkeiten, Zahlen in zwei nicht leere Teile aufzuteilen:
  • Zahlen bei Index 0 aufteilen. Dann ist der erste Teil [10] und seine Summe ist 10. Der zweite Teil ist [4,-8,7] und seine Summe ist 3. Da 10 >= 3 , i = 0 ist eine gültige Aufteilung.
  • Zahlen bei Index 1 aufteilen. Dann ist der erste Teil [10,4] und seine Summe ist 14. Der zweite Teil ist [-8,7] und seine Summe ist -1. Da 14 >= -1 ist, ist i = 1 eine gültige Aufteilung.
  • Zahlen bei Index 2 aufteilen. Dann ist der erste Teil [10,4,-8] und seine Summe ist 6. Der zweite Teil ist [7] und seine Summe ist 7. Da 6 < 7, i = 2 ist keine gültige Aufteilung.
  • Die Anzahl der gültigen Teilungen in Zahlen beträgt also 2.

Beispiel 2:

• Eingabe: nums = [2,3,1,0]
• Ausgabe: 2
• Erklärung: Es gibt zwei gültige Aufteilungen in Zahlen:
  • Zahlen bei Index 1 aufteilen. Dann ist der erste Teil [2,3] und seine Summe ist 5. Der zweite Teil ist [1,0] und seine Summe ist 1. Da 5 >= 1, i = 1 ist eine gültige Aufteilung.
  • Zahlen bei Index 2 aufteilen. Dann ist der erste Teil [2,3,1] und seine Summe ist 6. Der zweite Teil ist [0] und seine Summe ist 0. Da 6 >= 0, i = 2 ist eine gültige Aufteilung.

  Einschränkungen:

  • 2 <= nums.length <= 10⁵
  • -10⁵ <= nums[i] <= 10⁵

  Hinweis:

  1. Wie können wir für jeden Index i die Summe der ersten (i 1) Elemente aus der Summe der ersten i Elemente ermitteln?
  2. Wenn die Gesamtsumme des Arrays bekannt ist, wie können wir dann überprüfen, ob die Summe der ersten (i 1) Elemente größer oder gleich der Summe der übrigen Elemente ist?

  Lösung:

  Wir können es mit den folgenden Schritten angehen:

  Ansatz:

  1. Präfixsumme: Zuerst berechnen wir die kumulative Summe des Arrays von links, was bei der Überprüfung der Summe der ersten i 1 Elemente hilft.
  2. Gesamtsumme: Berechnen Sie die Gesamtsumme des Arrays. Dies ist nützlich, um zu überprüfen, ob die Summe der verbleibenden Elemente kleiner oder gleich der Summe der ersten i 1 Elemente ist.
  3. Über das Array iterieren: Für jeden gültigen Index i (wobei 0 <= i < n-1) prüfen wir, ob die Summe der ersten i 1 Elemente größer oder gleich der Summe von ist die letzten n-i-1 Elemente.
  4. Effizienz: Anstatt die Summen wiederholt neu zu berechnen, verwenden Sie für effiziente Vergleiche die Präfixsumme und die Gesamtsumme.

  Lassen Sie uns diese Lösung in PHP implementieren: 2270. Anzahl der Möglichkeiten, das Array aufzuteilen
  

  
  
  
  
  
  
    
    
    Erläuterung:
  
  
  
  
  $totalSum: Diese Variable speichert die Summe aller Elemente im Nums-Array.
  
  $prefixSum: Diese Variable verfolgt die kumulative Summe der Elemente von links (bis zum Index i).
  
  $remainingSum: Dies ist die Summe der verbleibenden Elemente vom Index i 1 bis zum Ende des Arrays. Es wird berechnet, indem $prefixSum von $totalSum subtrahiert wird.
  
  Valid Split Check: Für jeden Index i prüfen wir, ob die Präfixsumme größer oder gleich der verbleibenden Summe ist.
  
  
  
    
    
    Zeitkomplexität:
  
  
  
  
  O(n): Wir durchlaufen das Array einmal, um die Summe zu berechnen, und noch einmal, um nach gültigen Teilungen zu suchen. Daher ist die zeitliche Komplexität linear in Bezug auf die Länge des Arrays.
  
  
  
    
    
    Raumkomplexität:
  
  
  
  
  O(1): Wir verwenden nur wenige zusätzliche Variablen ($totalSum, $prefixSum, $remainingSum), daher ist die Raumkomplexität konstant.
  
  
  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 vonAnzahl der Möglichkeiten, das Array aufzuteilen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!