. Sous-tableau le plus court avec une somme d'au moins K

862. Sous-tableau le plus court avec une somme d'au moins K

Difficulté : Difficile

Sujets : Tableau, recherche binaire, file d'attente, fenêtre coulissante, tas (file d'attente prioritaire), somme de préfixes, file d'attente monotone

Étant donné un tableau entier nums et un entier k, renvoie la longueur du sous-tableau non vide le plus court de nums avec une somme d'au moins k. S'il n'existe pas un tel sous-tableau, retournez -1.

Un sous-tableau est une partie contiguë d'un tableau.

Exemple 1 :

• Entrée : nums = [1], k = 1
• Sortie : 1

Exemple 2 :

• Entrée : nums = [1,2], k = 4
• Sortie : -1

Exemple 3 :

• Entrée : nums = [2,-1,2], k = 3
• Sortie : 3

Contraintes :

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

Solution :

Nous devons utiliser une approche de fenêtre glissante combinée à des sommes de préfixes et une file d'attente monotone. Voici l'approche étape par étape :

Mesures:

1. Somme du préfixe :

   • Tout d'abord, calculez le tableau de somme de préfixes, où chaque élément à l'index i représente la somme des éléments depuis le début du tableau jusqu'à i. La somme des préfixes nous permet de calculer la somme de n'importe quel sous-tableau en temps constant.

2. File d'attente monotone :

   • Nous utilisons un deque (file d'attente à double extrémité) pour maintenir les indices du tableau prefix_sum. Le deque sera maintenu dans un ordre croissant de sommes de préfixes.
   • Cela nous aide à trouver efficacement des sous-tableaux dont la somme est supérieure ou égale à k en comparant la somme de préfixes actuelle avec les sommes de préfixes antérieures.

3. Logique de fenêtre coulissante :

   • Pour chaque index i, vérifiez si la différence entre la somme de préfixes actuelle et toute somme de préfixes précédente (qui est stockée dans le deque) est supérieure ou égale à k.
   • Si tel est le cas, calculez la longueur du sous-tableau et mettez à jour la longueur minimale si nécessaire.

Algorithme:

1. Initialisez le tableau prefix_sum avec une taille n 1 (où n est la longueur du tableau d'entrée). Le premier élément est 0 car la somme des éléments nuls est 0.
2. Utilisez un deque pour stocker les indices des valeurs prefix_sum. Le deque aidera à trouver le sous-réseau le plus court qui satisfait la condition de manière efficace.
3. Pour chaque élément du tableau, mettez à jour le prefix_sum et vérifiez le deque pour trouver le plus petit sous-tableau dont la somme est supérieure ou égale à k.

Implémentons cette solution en PHP : 862. Sous-tableau le plus court avec une somme d'au moins K

  
  
  Explication:




Tableau de somme de préfixes :


Nous calculons la somme cumulée du tableau dans le tableau prefix_sum. Cela aide à calculer la somme de tous les nombres de sous-tableaux[i...j] en utilisant la formule prefix_sum[j 1] - prefix_sum[i].



File d'attente monotone :


Le deque contient les indices du tableau prefix_sum par ordre croissant de valeurs. Nous maintenons cet ordre afin de pouvoir trouver efficacement le plus petit sous-tableau dont la somme est supérieure ou égale à k.



Logique de fenêtre coulissante :


Lorsque nous parcourons le tableau prefix_sum, nous essayons de trouver le plus petit sous-tableau en utilisant la différence entre le prefix_sum[i] actuel et le prefix_sum[deque[0]] précédent.
Si la différence est supérieure ou égale à k, nous calculons la longueur du sous-tableau et mettons à jour la longueur minimale trouvée.



Résultat de retour :


Si aucun sous-tableau valide n'est trouvé, renvoyez -1. Sinon, renvoie la longueur minimale du sous-tableau.





  
  
  Complexité temporelle :




Complexité temporelle : O(n), où n est la longueur du tableau d'entrée. Chaque élément est traité au maximum deux fois (une fois lorsqu'il est ajouté au deque et une fois lorsqu'il est supprimé).

Complexité spatiale : O(n) en raison du tableau prefix_sum et du deque utilisé pour stocker les indices.


Cette approche garantit que la solution fonctionne efficacement, même pour des intrants importants.

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!