2270. Nombre de façons de diviser le tableau

difficulté: medium

sujets: array, préfixe sum

vous avez un 0 indexé Array entier num de longueur n.

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

• La somme des premiers éléments i 1 est supérieur ou égal à la somme du dernier n - i - 1 éléments.
• il y a au moins un élément à droite de i. C'est-à-dire 0

return Le nombre de valide les divisions dans nums .

Exemple 1:

• entrée: nums = [10,4, -8,7]
• output: 2
• Explication: Il existe trois façons de diviser les numéros en deux parties non vides:
  • diviser les numéros à 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 une division valide.
  • diviser les numéros à 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. Depuis 14> = -1, i = 1 est une division valide.
  • Split nums à 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. Depuis 6
  • Ainsi, le nombre de divisions valides en nums est 2.

Exemple 2:

• entrée: nums = [2,3,1,0]
• output: 2
• Explication: Il y a deux divisions valides en nums:
  • divisé les numéros à 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 division valide.
  • Split nums à 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 une division valide.

contraintes:

• 2 5
• - 10 ⁵ 5

Indice:

1. pour tout index i, comment pouvons-nous trouver la somme des premiers (i 1) des éléments de la somme des premiers éléments i?
2. Si la somme totale du tableau est connue, comment pouvons-nous vérifier si la somme des premiers (i 1) éléments supérieurs ou égaux aux éléments restants?

Solution:

nous pouvons l'aborder en utilisant les étapes suivantes:

Approche:

1. préfixe sum : Premièrement, nous calculons la somme cumulative du tableau de la gauche, ce qui aide à vérifier la somme des premiers éléments i 1.
2. somme totale : calculer la somme totale du tableau, qui est utile pour vérifier si la somme des éléments restants est inférieur ou égal à la somme des premiers éléments i 1.
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 dans php: 2270. Nombre de façons de diviser le tableau

Explication:

1. $ totalsum : Cette variable stocke la somme de tous les éléments du tableau Nums.
2. $ prefixsum : Cette variable garde une trace de la somme cumulative des éléments de la gauche (jusqu'à l'index i).
3. $ restingsum : Il s'agit de la somme des éléments restants de l'index I 1 à la fin du tableau. Il est calculé en soustrayant $ prefixsum de $ totalsum.
4. Valide Split Check : Pour chaque index i, nous vérifions si la somme du préfixe est supérieure ou égale à la somme restante.

Complexité du temps:

• o (n) : Nous parcourons le tableau une fois pour calculer la somme et encore une fois pour vérifier les fentes valides. Par conséquent, la complexité du temps est linéaire par rapport à la longueur du tableau.

Complexité de l'espace:

• o (1) : Nous n'utilisons que quelques variables supplémentaires ($ totalsum, $ prefixsum, $ restingsum), donc la complexité de l'espace est constante.

liens de contact

Si vous avez trouvé cette série utile, veuillez envisager de donner le référentiel une étoile sur GitHub ou de partager le message sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi!

Si vous voulez un contenu plus utile comme celui-ci, n'hésitez pas à me suivre:

• linkedIn
• github