Maison >développement back-end >tutoriel php >Nombre de façons de diviser un tableau

Nombre de façons de diviser un tableau

Barbara Streisand
Barbara Streisandoriginal
2025-01-06 01:56:41828parcourir

Number of Ways to Split Array

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 <= 105
    • -105 <= nums[i] <= 105

    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:

    1. $totalSum : Cette variable stocke la somme de tous les éléments du tableau nums.
    2. $prefixSum : Cette variable garde la trace de la somme cumulée des éléments de gauche (jusqu'à l'index i).
    3. $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.
    4. 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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn