Somme de plage des sommes de sous-tableaux triés

1508. Somme de plage des sommes de sous-tableaux triés

Moyen

Vous recevez le tableau numérique composé de n entiers positifs. Vous avez calculé la somme de tous les sous-tableaux continus non vides du tableau, puis les avez triés dans un ordre non décroissant, créant un nouveau tableau de n * (n + 1) / 2 nombres.

Renvoyer la somme des nombres de l'index gauche à l'index droit (indexé à partir de 1), inclus, dans le nouveau tableau. Puisque la réponse peut être un nombre énorme, renvoyez-la modulo 10⁹ + 7.

Exemple 1 :

• Entrée : nums = [1,2,3,4], n = 4, gauche = 1, droite = 5
• Sortie : 13
• Explication : Toutes les sommes des sous-tableaux sont 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. Après les avoir triées dans un ordre non décroissant, nous avons le nouveau tableau [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. La somme des nombres de l'indice le = 1 à ri = 5 est 1 + 2 + 3 + 3 + 4 = 13.

Exemple 2 :

• Entrée : nums = [1,2,3,4], n = 4, gauche = 3, droite = 4
• Sortie : 6
• Explication : Le tableau donné est le même que celui de l'exemple 1. Nous avons le nouveau tableau [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. La somme des nombres de l'index le = 3 à ri = 4 est 3 + 3 = 6.

Exemple 3 :

• Entrée : nums = [1,2,3,4], n = 4, gauche = 1, droite = 10
• Sortie : 50

Contraintes :

• n == nums.length
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100
• 1 <= gauche <= droite <= n * (n + 1) / 2

Indice :

1. Calculez toutes les sommes et enregistrez-les dans un tableau.
2. Ensuite, passez simplement de l'index GAUCHE à DROITE et calculez la réponse modulo 1e9 + 7.

Solution :

Pour résoudre ce problème, nous pouvons suivre ces étapes :

1. Générez toutes les sommes possibles de sous-tableaux continus non vides.
2. Triez le tableau de sommes obtenu.
3. Calculez la somme des éléments de l'index de gauche à l'index de droite (basé sur 1).
4. Renvoyer le résultat modulo 10⁹ + 7.

Implémentons cette solution en PHP : 1508. Somme de plage des sommes de sous-tableaux triés

  
  
  Explication:




Génération de sommes de sous-tableaux :


Parcourez chaque index de départ i du sous-tableau.
Pour chaque index de départ i, calculez la somme des sous-tableaux se terminant à l'index j (où j >= i).
Ajoutez chaque somme de sous-tableau calculée au tableau $sums.



Tri des sommes :


Utilisez la fonction sort() de PHP pour trier le tableau $sums dans un ordre non décroissant.



Résumation de la plage requise :


Itérer de l'index gauche-1 à l'index droite-1 (puisque le problème utilise l'indexation basée sur 1).
Accumulez la somme des éléments de cette plage en prenant soin d'utiliser modulo 109 + 7 pour éviter les débordements.




Cette solution génère efficacement toutes les sommes des sous-tableaux, les trie et calcule la somme de plage requise comme spécifié.

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!