Programme JavaScript pour calculer des triplets dont la somme est inférieure à une valeur donnée

Nous allons écrire un programme JavaScript pour compter le nombre de triplets dont la somme est inférieure à une valeur donnée. Ce problème peut être résolu en triant le tableau et en utilisant deux pointeurs pour vérifier les combinaisons possibles. Tout d’abord, nous allons trier le tableau par ordre croissant, puis, pour chaque élément du tableau, nous utiliserons deux pointeurs pour rechercher les triples dont la somme est inférieure à la valeur donnée. Le nombre de ces triples sera le décompte que nous suivrons.

De plus, nous mettrons à jour le décompte et le pointeur en fonction de la somme des triples inférieure ou égale à la valeur donnée. De cette façon, nous pouvons résoudre le problème efficacement avec une complexité temporelle O(n^2). C'est une technique très utile à retenir en cas de problèmes futurs où nous devrons trouver des décomptes pour certaines combinaisons qui satisfont certaines conditions.

Enfin, nous renverrons le nombre de ces triples dont la somme est inférieure à la valeur donnée.

Méthode

• Tout d’abord, triez le tableau de nombres donné par ordre croissant.

• Initialisez trois variables : gauche, droite et nombre.

• Ensuite, utilisez la méthode à deux pointeurs, le pointeur gauche commence à 0 et le pointeur droit commence à la fin.

• Pour chaque itération, calculez la somme du triplet actuel (élément pointant vers la gauche + élément pointant vers la droite + élément actuel).

• Si la somme est inférieure à la valeur donnée, incrémentez le décompte et le pointeur gauche.

• Si la somme est supérieure à la valeur donnée, décrémentez le pointeur droit. Répétez ce processus jusqu'à ce que le pointeur gauche soit plus petit que le pointeur droit.

Exemple

Ceci est un exemple complet de programme JavaScript pour compter le nombre de triplets dont la somme est inférieure à une valeur donnée -

function countTriplets(arr, sum) {
   let count = 0;
   arr.sort((a, b) => a - b); 
   // sorting the array in ascending order
   for (let i = 0; i < arr.length - 2; i++) {
      let left = i + 1;
      let right = arr.length - 1;
      while (left < right) {
         if (arr[i] + arr[left] + arr[right] >= sum) {
         right--;
         } else {
            count += right - left;
            left++;
         }
      }
   }
   return count;
}
const arr = [5, 1, 3, 4, 7];
const sum = 12;
console.log(countTriplets(arr, sum));

Instructions

La fonction

• countTriplets prend le tableau arr et la valeur sum comme arguments.

La variable

• count garde une trace du nombre de triples dont la somme est inférieure à sum.

• arr Trier par ordre croissant à l'aide de la fonction de tri.

• Boucle externefor (let i = 0; i itère le tableau, avec les pointeurs left et right initialisés à l'index suivant de i et au dernier index du tableau respectivement.

• while (gauche La boucle continue jusqu'à ce que le pointeur gauche soit supérieur ou égal au pointeur droite.

• while (gauche La boucle continue jusqu'à ce que le pointeur gauche soit supérieur ou égal au pointeur droit.

• Dans chaque itération de la boucle while, ​​arr[i], arr[left], et arr[right] sont calculés. Si cette somme est supérieure ou égale à la somme , alors le pointeur droit est décrémenté. Si la somme est inférieure à la sum, alors le count sera incrémenté du nombre d'éléments restants entre les pointeurs left et rightb>, et le pointeur left sera incrémenté.

La fonction

• renvoie la variable count, qui représente le nombre de triplets dont la somme est inférieure à sum.

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!