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

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
  • 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 5
• -10⁵ 5

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
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

<?php /**
 * @param Integer[] $nums
 * @return Integer
 */
function waysToSplitArray($nums) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [10, 4, -8, 7];
echo waysToSplitArray($nums1); // Output: 2

$nums2 = [2, 3, 1, 0];
echo waysToSplitArray($nums2); // Output: 2
?>

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!