2270. Anzahl der Möglichkeiten, Array zu teilen

Schwierigkeitsgrad: medium

themen: array, Präfix sum

Sie erhalten eine 0-indexed Integer Array nums der Länge n.

nums enthält eine valte split unter Index I Wenn Folgendes wahr ist:

• Die Summe der ersten I 1 -Elemente ist größer als oder gleich die Summe der letzten n - i - 1 Elemente.
• da ist mindestens ein Element rechts von i. Das heißt, 0

return die Nummer von gültige Splits in nums .

Beispiel 1:

• input: nums = [10,4, -8,7]
• output: 2
• Erläuterung: Es gibt drei Möglichkeiten, NUMs in zwei nicht leere Teile aufzuteilen:
  • trenc nums am Index 0. Dann ist der erste Teil [10], und seine Summe beträgt 10. Der zweite Teil ist [4, -8,7], und seine Summe beträgt 3.. Da 10> = 3, i = 0 eine gültige Spaltung ist.
  • trenc nums im Index 1. Dann ist der erste Teil [10,4], und seine Summe beträgt 14. Der zweite Teil ist [-8,7] und seine Summe ist -1. Da 14> = -1, ist i = 1 eine gültige Spaltung.
  • trenc nums auf Index 2. Dann ist der erste Teil [10,4, -8], und seine Summe beträgt 6. Der zweite Teil ist [7], und seine Summe beträgt 7. Da 6
  • Somit ist die Anzahl der gültigen Spaltungen in NUMS 2.

Beispiel 2:

• input: nums = [2,3,1,0]
• output: 2
• Erläuterung: Es gibt zwei gültige Spaltungen in NUMs:
  • trenc nums im Index 1. Dann ist der erste Teil [2,3], und seine Summe beträgt 5. Der zweite Teil ist [1,0], und seine Summe beträgt 1. Da 5> = 1, ist i = 1 eine gültige Spaltung.
  • trenc nums am Index 2. Dann ist der erste Teil [2,3,1], und seine Summe beträgt 6. Der zweite Teil ist [0], und seine Summe beträgt 0. Da 6> = 0, ist i = 2 eine gültige Spaltung.

Einschränkungen:

• 2 5
• -10 ⁵ 5

Hinweis:

1. Für jeden Index I finden wir die Summe der ersten (i 1) Elemente aus der Summe der ersten I -Elemente?
2. Wenn die Gesamtsumme des Arrays bekannt ist

Lösung:

1. prefix sum : Zunächst berechnen wir die kumulative Summe des Arrays von links, was hilft, die Summe der ersten I 1 -Elemente zu überprüfen.
2. Total Sum : Berechnen Sie die Gesamtsumme des Arrays, was bei der Überprüfung der Summe der verbleibenden Elemente nützlich ist
iterieren Sie über das Array
3. : Für jeden gültigen Index I (wobei 0
efficiency
4. : Verwenden Sie die Präfixsumme und die Gesamtsumme für effiziente Vergleiche, anstatt die Summen wiederholt neu zu berechnen.
Lassen Sie uns diese Lösung in PHP implementieren:

php /** * @param Integer [] $ nums * @return Integer */ Funktion WayStosplitarray ($ nums) { ... ... ... /** * Gehen Sie zu ./solution.php */ } // Beispiel Verwendung: $ nums1 = [10, 4, -8, 7]; echo WayStosplitarray ($ nums1); // Ausgabe: 2 $ nums2 = [2, 3, 1, 0]; echo WayStosplitarray ($ nums2); // Ausgabe: 2 ?>

$ totalsum
1. : Diese Variable speichert die Summe aller Elemente im NUMS -Array.
$ prefixsum
2. : Diese Variable verfolgt die kumulative Summe von Elementen von links (bis in den Index i).
$ realingsum
3. : Dies ist die Summe der verbleibenden Elemente von Index I 1 bis zum Ende des Arrays. Es wird berechnet, indem $ $ prefixsum von $ sotalalumum subtrahiert werden.
Gültiger Split -Check
4. : Für jeden Index I überprüfen wir, ob die Präfix -Summe größer oder gleich der verbleibenden Summe ist.
Zeitkomplexität:

o (n)
• : Wir gehen einmal durch das Array, um die Summe zu berechnen und erneut nach gültigen Spaltungen zu überprüfen. Daher ist die Zeitkomplexität in Bezug auf die Länge des Arrays linear.
Raumkomplexität:

o (1)
• : Wir verwenden nur ein paar zusätzliche Variablen ($ Totalsum, $ Präfixsum, $ restalsum), daher ist die Raumkomplexität konstant.

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie den

einen Stern auf Github geben oder den Beitrag in Ihren Lieblingsnetzwerken teilen? Ihre Unterstützung würde mir viel bedeuten! Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

linkedIn
github