Nombre de façons de diviser un tableau

2270. Nombre de façons de diviser un tableau

Difficulté :Moyen

Sujets : Tableau, somme de préfixe

Vous recevez un tableau de nombres entiers indexé à 0 de longueur n.

nums contient un partage valide à l'index i si les éléments suivants sont vrais :

• La somme des i 1 premiers éléments est supérieure ou égale à la somme des n - i - 1 derniers éléments.
• Il y a au moins un élément à droite de i. Autrement dit, 0 <= i < n-1.

Renvoyer le nombre de spartitions valides en chiffres.

Exemple 1 :

• Entrée : nums = [10,4,-8,7]
• Sortie : 2
• Explication : Il existe trois façons de diviser des nombres en deux parties non vides :
  • Divisez les nombres à l'index 0. Ensuite, la première partie est [10] et sa somme est 10. La deuxième partie est [4,-8,7] et sa somme est 3. Puisque 10 >= 3 , i = 0 est un partage valide.
  • Divisez les nombres à l'index 1. Ensuite, la première partie est [10,4] et sa somme est 14. La deuxième partie est [-8,7] et sa somme est -1. Puisque 14 >= -1, i = 1 est une répartition valide.
  • Divisez les nombres à l'index 2. Ensuite, la première partie est [10,4,-8] et sa somme est 6. La deuxième partie est [7] et sa somme est 7. Puisque 6 < 7, i = 2 n'est pas une répartition valide.
  • Ainsi, le nombre de fractionnements valides en nombres est de 2.

Exemple 2 :

• Entrée : nums = [2,3,1,0]
• Sortie : 2
• Explication : Il existe deux divisions valides en nombres :
  • Divisez les nombres à l'index 1. Ensuite, la première partie est [2,3] et sa somme est 5. La deuxième partie est [1,0] et sa somme est 1. Puisque 5 >= 1, i = 1 est une répartition valide.
  • Divisez les nombres à l'index 2. Ensuite, la première partie est [2,3,1] et sa somme est 6. La deuxième partie est [0] et sa somme est 0. Puisque 6 >= 0, i = 2 est un partage valide.

  Contraintes :

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

  Indice :

  1. Pour tout indice i, comment pouvons-nous trouver la somme des premiers (i 1) éléments à partir de la somme des i premiers éléments ?
  2. Si la somme totale du tableau est connue, comment pouvons-nous vérifier si la somme des premiers (i 1) éléments est supérieure ou égale aux éléments restants ?

  Solution :

  Nous pouvons l'aborder en suivant les étapes suivantes :

  Approche:

  1. Somme des préfixes : Tout d'abord, nous calculons la somme cumulée du tableau à partir de la gauche, ce qui aide à vérifier la somme des i 1 premiers éléments.
  2. Somme totale : calculez la somme totale du tableau, ce qui est utile pour vérifier si la somme des éléments restants est inférieure ou égale à la somme des i 1 premiers éléments.
  3. Itérer sur le tableau : Pour chaque index valide i (où 0 <= i < n-1), on vérifie si la somme des i 1 premiers éléments est supérieure ou égale à la somme de les derniers éléments n-i-1.
  4. Efficacité : Au lieu de recalculer les sommes à plusieurs reprises, utilisez la somme du préfixe et la somme totale pour des comparaisons efficaces.

  Implémentons cette solution en PHP : 2270. Nombre de façons de diviser un tableau
  

  
  
  
  
  
  
    
    
    Explication:
  
  
  
  
  $totalSum : Cette variable stocke la somme de tous les éléments du tableau nums.
  
  $prefixSum : Cette variable garde la trace de la somme cumulée des éléments de gauche (jusqu'à l'index i).
  
  $remainingSum : C'est la somme des éléments restants de l'index i 1 jusqu'à la fin du tableau. Il est calculé en soustrayant $prefixSum de $totalSum.
  
  Valid Split Check : Pour chaque index i, nous vérifions si la somme des préfixes est supérieure ou égale à la somme restante.
  
  
  
    
    
    Complexité temporelle :
  
  
  
  
  O(n) : Nous parcourons le tableau une fois pour calculer la somme et encore une fois pour vérifier les divisions valides. Par conséquent, la complexité temporelle est linéaire par rapport à la longueur du tableau.
  
  
  
    
    
    Complexité spatiale :
  
  
  
  
  O(1) : Nous n'utilisons que quelques variables supplémentaires ($totalSum, $prefixSum, $remainingSum), donc la complexité spatiale est constante.
  
  
  Liens de contact
  
  Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !
  
  Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :
  
  
  LinkedIn
  GitHub
  
  
  
            
  
              
    
  
              
          

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!