Programme JavaScript à deux pointeurs

La technologie à double pointeur pour les programmes JavaScript est une méthode algorithmique couramment utilisée pour résoudre divers problèmes nécessitant une complexité temporelle linéaire. Cette technique est largement utilisée pour résoudre des problèmes de recherche, de tri ou de manipulation de tableaux, de chaînes ou de listes chaînées. Cette méthode fonctionne en conservant deux pointeurs, l'un commençant au début de la structure de données et l'autre à partir de la fin, puis en les parcourant dans la direction opposée jusqu'à ce qu'une solution soit trouvée.

Dans ce tutoriel, nous explorerons le concept de technique de double pointeur et comment l'implémenter à l'aide du langage de programmation JavaScript. Commençons donc par l’énoncé du problème, puis passons à autre chose avec ce tutoriel amusant !

Énoncé du problème

Étant donné un tableau A trié par ordre croissant, contenant N entiers, vérifiez s'il existe une paire d'éléments (A[i], A[j]) telle que leur somme soit égale à X.

Comprenons maintenant le fonctionnement du programme ci-dessus à travers quelques exemples.

Input: const array = [1, 3, 5, 7, 9];
   const X = 12;
Output: Pair found at indices 1 and 4

Explication - Dans ce cas, la paire d'éléments (3, 9) dans le tableau d'entrée est ajoutée pour donner la somme cible de 12, et le programme identifie correctement la paire d'éléments avec les index 1 et 4.

Input: const array = [1, 3, 5, 7, 9];
   const X = 9;
Output: Pair not found

Explication - Dans ce cas, si la somme cible est de 9, alors aucune paire de ce type n'existe et la fonction doit renvoyer "paire non trouvée".

Algorithme

Algorithme utilisant l'astuce du double pointeur pour savoir s'il existe une paire d'éléments dans un tableau trié dont la somme est égale à une valeur cible donnée -

• Initialisez deux pointeurs, gauche = 0, droite = longueur du tableau - 1.

• Lorsque le côté gauche est plus petit que le côté droit, effectuez les opérations suivantes

  • Calculez la somme des éléments à l'index gauche et droit.

  • Si la somme est égale à la valeur cible, renvoyez l'index gauche et l'index droit.

  • Si la somme est inférieure à la valeur cible, ajoutez la gauche.

  • Si la somme est supérieure à la valeur cible, diminuez le côté droit.

• Si aucune paire de ce type n’existe, renvoyez null.

L'algorithme ci-dessus utilise la technique du double pointeur pour rechercher une paire d'éléments dans un tableau trié de telle sorte que leur somme soit égale à une valeur cible donnée. Les pointeurs commencent à chaque extrémité du tableau et se déplacent les uns vers les autres en fonction de la comparaison de la somme des éléments au niveau du pointeur avec la valeur cible. Si la somme est inférieure à la valeur cible, déplacez le pointeur gauche vers la droite pour augmenter la somme. Si la somme est supérieure à la valeur cible, déplacez le pointeur droit vers la gauche pour diminuer la somme. Si la somme est égale à la valeur cible, le programme renvoie l'index de la paire d'éléments. Si aucune paire d’éléments de ce type n’existe, le programme renvoie Pair Not Found.

Comprenons maintenant cet algorithme à travers un exemple, dans cet exemple, nous utiliserons JavaScript pour implémenter l'énoncé du problème discuté précédemment.

La traduction chinoise de

Exemple

est :

Exemple

Dans ce programme, nous avons utilisé la technique des deux pointeurs pour déterminer s'il existe une paire d'éléments dans un tableau trié donné dont la somme est égale à une cible donnée en parcourant le tableau et en déplaçant les pointeurs en fonction de la somme des éléments au niveau du tableau. pointeurs, le programme trouve efficacement la paire d'éléments (si elle existe) dans une complexité temporelle O(N), où N est le nombre d'éléments dans le tableau.

function findSumPair(array, X) {
   let left = 0;
   let right = array.length - 1;
   while (left < right) {
      const sum = array[left] + array[right];
      if (sum === X) {
         console.log(`Pair found at indices ${left} and ${right}`);
         return [left, right];
      } else if (sum < X) {
         left++;
      } else {
         right--;
      }
   }
   console.log('Pair not found');
   return null;
}
const array = [1, 3, 5, 7, 9];
const X = 12;
console.log(`Array: ${array}`);
console.log(`Target sum: ${X}`);
findSumPair(array, X);

Conclusion

Dans ce didacticiel, nous avons exploré le concept de technique de double pointeur et comment l'implémenter à l'aide du langage de programmation JavaScript pour résoudre des problèmes impliquant la recherche ou la comparaison d'une paire d'éléments dans un tableau trié. Nous avons également appris un algorithme permettant de trouver une paire d'éléments tels que leur somme soit égale à une cible donnée en utilisant la technique des deux pointeurs. En utilisant cette technique, nous pouvons améliorer considérablement l’efficacité de notre programme en termes de complexité temporelle. Plus précisément, la technologie du double pointeur peut résoudre ce type de problème dans une complexité temporelle de O(N), ce qui est beaucoup plus rapide que la méthode par force brute de O(N^2). Il est donc très important d’apprendre et d’appliquer cette technique pour résoudre efficacement des problèmes similaires.

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!