JavaScript 程序计算总和小于给定值的三元组

我们将编写一个 JavaScript 程序来计算总和小于给定值的三元组的数量。这个问题可以通过对数组进行排序并使用两个指针来检查可能的组合来解决。首先，我们按升序对数组进行排序，然后，对于数组中的每个元素，我们将使用两个指针来检查总和小于给定值的三元组。这样的三元组的数量将是我们将跟踪的计数。

此外，我们将根据三元组之和小于或等于给定值来更新计数和指针。这样，我们就能以 O(n^2) 的时间复杂度高效地解决问题。这是一种非常有用的技术，需要记住，以应对未来的问题，我们需要找到满足特定条件的某些组合的计数。

最后，我们将返回总和小于给定值的此类三元组的计数。

方法

• 首先，按升序对给定的数字数组进行排序。

• 初始化三个变量：left、right 和 count。

• 然后使用两个指针的方法，左指针从0开始，右指针从end开始。

• 对于每次迭代，计算当前三元组的总和（左指向的元素+右指向的元素+当前元素）。

• 如果总和小于给定值，则增加计数和左指针。

• 如果总和大于给定值，则递减右指针。重复该过程，直到左指针小于右指针。

示例

这是一个 JavaScript 程序的完整示例，用于计算总和小于给定值的三元组的数量 -

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));

说明

• countTriplets 函数采用数组 arr 和值 sum 作为其参数。

• count 变量用于跟踪总和小于 sum 的三元组的数量。

• arr 使用排序函数按升序排序。

• 外循环for (let i = 0; i < arr.length - 2; i++)迭代数组，left和< b>right 指针分别初始化为 i 的下一个索引和数组的最后一个索引。

• while (left < right) 循环继续进行，直到 left 指针大于或等于 right 指针。

• while (left < right)循环一直持续，直到左指针大于或等于右指针。

• 在while循环的每次迭代中，arr[i]、arr[left]、和arr[right]<的总和/b> 已计算。如果该总和大于或等于总和，则右指针递减。如果总和小于总和，则计数将增加左和右之间剩余元素的数量b> 指针，left 指针递增。

• 函数返回count变量，它表示总和小于sum的三元组的数量。