Somme maximale des sous-réseaux distincts de longueur K

2461. Somme maximale des sous-tableaux distincts de longueur K

Difficulté :Moyen

Sujets : Tableau, table de hachage, fenêtre coulissante

Vous recevez un tableau entier nums et un entier k. Trouvez la somme maximale des sous-tableaux de tous les sous-tableaux de nombres qui remplissent les conditions suivantes :

• La longueur du sous-tableau est k, et
• Tous les éléments du sous-tableau sont distincts.

Renvoyer la somme maximale des sous-tableaux de tous les sous-tableaux qui remplissent les conditions. Si aucun sous-tableau ne remplit les conditions, renvoie 0.

Un sous-tableau est une séquence contiguë non vide d'éléments au sein d'un tableau.

Exemple 1 :

• Entrée : nums = [1,5,4,2,9,9,9], k = 3
• Sortie : 15
• Explication : Les sous-tableaux de nombres de longueur 3 sont :
  • [1,5,4] qui répond aux exigences et a une somme de 10.
  • [5,4,2] qui répond aux exigences et a une somme de 11.
  • [4,2,9] qui répond aux exigences et a une somme de 15.
  • [2,9,9] qui ne répond pas aux exigences car l'élément 9 est répété.
  • [9,9,9] qui ne répond pas aux exigences car l'élément 9 est répété.
  • Nous renvoyons 15 car c'est la somme maximale des sous-tableaux de tous les sous-tableaux qui remplissent les conditions

Exemple 2 :

• Entrée : nums = [4,4,4], k = 3
• Sortie : 0
• Explication : Les sous-tableaux de nombres de longueur 3 sont :
  • [4,4,4] qui ne répond pas aux exigences car l'élément 4 est répété.
  • Nous renvoyons 0 car aucun sous-tableau ne remplit les conditions.

Contraintes :

• 1 <= k <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁵

Indice :

1. Quels éléments changent lors du passage du sous-tableau de taille k qui se termine à l'index i au sous-tableau de taille k qui se termine à l'index i 1 ?
2. Seuls deux éléments changent, l'élément en i 1 est ajouté au sous-tableau et l'élément en i - k 1 est supprimé du sous-tableau.
3. Parcourez chaque sous-tableau de taille k et gardez une trace de la somme du sous-tableau et de la fréquence de chaque élément.

Solution :

Nous pouvons suivre ces étapes :

Approche:

1. Fenêtre coulissante : La taille de la fenêtre est k, et nous faisons glisser la fenêtre à travers le tableau tout en conservant la somme de la fenêtre actuelle et en vérifiant si tous les éléments de la fenêtre sont distincts.
2. Table de hachage (ou tableau associatif) : utilisez un tableau associatif (table de hachage) pour suivre la fréquence des éléments dans la fenêtre actuelle. Si un élément apparaît plus d'une fois, la fenêtre n'est pas valide.
3. Mise à jour de la fenêtre : Au fur et à mesure que nous faisons glisser la fenêtre, ajoutez le nouvel élément (c'est-à-dire l'élément entrant dans la fenêtre) et supprimez l'ancien élément (c'est-à-dire l'élément quittant la fenêtre). Mettez à jour la somme en conséquence et vérifiez si la fenêtre est valide (c'est-à-dire que tous les éléments sont distincts).
4. Renvoyer la somme maximale : nous devons garder une trace de la somme maximale rencontrée parmi les sous-tableaux valides.

Algorithme:

1. Initialisez une fréquence de table de hachage pour stocker la fréquence des éléments dans la fenêtre actuelle.
2. Commencez par calculer la somme pour la première fenêtre de taille k et stockez le résultat si la fenêtre contient des éléments distincts.
3. Faites glisser la fenêtre de gauche à droite en :
   • Suppression de l'élément qui sort de la fenêtre par la gauche.
   • Ajout de l'élément qui entre dans la fenêtre par la droite.
   • Mettez à jour la somme et la table de hachage, et vérifiez si la fenêtre ne contient toujours que des éléments distincts.
4. Si la fenêtre comporte des éléments distincts valides, mettez à jour la somme maximale.
5. Si aucun sous-tableau valide n'est trouvé, renvoyez 0.

Implémentons cette solution en PHP : 2461. Somme maximale des sous-tableaux distincts de longueur K

  
  
  Explication:




Variables :



$maxSum : suit la somme maximale d'un sous-tableau valide trouvé jusqu'à présent.

$currentSum : contient la somme de la fenêtre glissante actuelle de taille k.

$freq : Une table de hachage (ou tableau associatif) qui stocke la fréquence des éléments dans la fenêtre actuelle.



Fenêtre coulissante :


Nous parcourons le tableau avec une boucle. En déplaçant la fenêtre, nous :


Ajoutez l'élément à l'index $i à la somme et mettez à jour sa fréquence.
Si la taille de la fenêtre dépasse k, nous supprimons l'élément à l'index $i - k de la somme et réduisons sa fréquence.





Vérification de fenêtre valide :


Une fois que la taille de la fenêtre atteint k (c'est-à-dire lorsque $i >= k - 1), nous vérifions si tous les éléments de la fenêtre sont distincts en nous assurant que le nombre de clés distinctes dans la carte de fréquence est égal à k. Si c'est le cas, nous mettons à jour la somme maximale.



Renvoyer le résultat :

Après avoir parcouru le tableau, nous renvoyons la somme maximale trouvée. Si aucun sous-tableau valide n'a été trouvé, maxSum restera 0.





  
  
  Complexité temporelle :




O(n), où n est la longueur du tableau nums. Chaque élément est ajouté et supprimé de la fenêtre coulissante une fois, et les opérations de table de hachage (insertion, suppression, nombre de vérifications) sont O(1) en moyenne.



  
  
  Complexité spatiale :




O(k) pour la table de hachage qui stocke la fréquence des éléments dans la fenêtre actuelle.


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!