Résolution efficace de deux sommes II - Le tableau d'entrée est trié

Le problème « Two Sum II – Le tableau d'entrée est trié » est un défi de codage classique qui teste votre compréhension des tableaux et de la manipulation des pointeurs. C’est aussi une belle opportunité de présenter une solution à la fois élégante et efficace. Plongeons dans le problème et décomposons une approche optimale pour le résoudre.

Lien vers le problème sur LeetCode

Énoncé du problème

Étant donné un tableau de nombres entiers indexés sur 1 triés par ordre non décroissant, votre objectif est de trouver deux nombres tels que leur somme soit égale à un objectif donné. Vous devez renvoyer les indices de ces deux nombres sous forme de tableau [index1, index2] où 1 <= index1 < index2 <= nombres.longueur. La solution ne doit utiliser qu'un espace supplémentaire constant.

Contraintes

• Les numéros du tableau sont triés par ordre non décroissant.
• Il existe exactement une solution.
• Vous ne pouvez pas utiliser deux fois le même élément.
• La longueur du tableau d'entrée varie de 2 à 30 000.
• Les valeurs du tableau vont de −1 000 à 1 000.

Exemples d'entrées et de sorties

1. Entrée : nombres = [2,7,11,15], cible = 9
   
   Sortie : [1, 2]

2. Entrée : nombres = [2,3,4], cible = 6
   
   Sortie : [1, 3]

3. Entrée : nombres = [-1,0], cible = -1
   
   Sortie : [1, 2]

Approche : deux indicateurs

Les contraintes du problème (un tableau trié et une solution unique) en font un candidat parfait pour la technique à deux pointeurs. Voici pourquoi :

• Efficacité : Deux pointeurs nous permettent de parcourir le tableau en un seul passage (complexité temporelle O(n)).
• Espace constant : Nous évitons les structures de données auxiliaires, en respectant l'exigence du problème d'un espace supplémentaire constant.

Mise en œuvre

Vous trouverez ci-dessous l'implémentation JavaScript de l'approche à deux points :

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};






  
  
  Comment ça marche




Initialiser deux pointeurs :



leftPointer commence au début du tableau.

rightPointer commence à la fin du tableau.



Itérer jusqu'à ce qu'ils se rencontrent :


Calculez la somme des éléments à leftPointer et rightPointer.
Si la somme correspond à l'objectif, renvoie les positions indexées 1.
Si la somme est supérieure à l'objectif, décrémentez le rightPointer pour réduire la somme.
Si la somme est inférieure à l'objectif, incrémentez le leftPointer pour augmenter la somme.



Renvoyer les indices :

Une fois la bonne paire trouvée, la boucle se termine et renvoie les indices.





  
  
  Exemple de procédure pas à pas


Parcourons le premier exemple :



Entrée : nombres = [2, 7, 11, 15], cible = 9


Initialisation : leftPointer = 0, rightPointer = 3




  
  
  Étapes d'itération :



Calculez les nombres[0] nombres[3] = 2 15 = 17. 


Trop grand, décrémenter le pointeur à droite à 2.


Calculez les nombres[0] nombres[2] = 2 11 = 13. 


Encore trop grand, décrémenter le pointeur à droite à 1.


Calculez les nombres[0] nombres[1] = 2 7 = 9. 


Correspondance trouvée, renvoie [1, 2].





  
  
  Points clés




1-Ajustement indexé : Le problème spécifie une indexation basée sur 1, nous ajoutons donc 1 aux deux pointeurs avant de revenir.

Cas Edge : Les contraintes garantissent une solution unique, nous n'avons donc pas besoin de gérer des tableaux vides ou plusieurs correspondances.

Optimisation : L'utilisation de l'approche à deux points garantit que nous répondons à la complexité temporelle O(n) et aux exigences d'espace constantes.



  
  
  Conclusion


La méthode à deux pointeurs résout élégamment le problème « Two Sum II - Le tableau d'entrée est trié » en exploitant la nature triée du tableau d'entrée. Il s’agit d’une technique puissante qui non seulement garantit l’efficacité, mais respecte également les contraintes d’espace, ce qui en fait une approche incontournable pour des problèmes similaires. Bon codage !


          

            
        
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!