JavaScript 计算小于给定值的三元组数量
我们将编写一个JavaScript程序来计算小于给定值的三元组的数量。这个问题可以通过排序数组并使用两个指针来检查可能的组合来解决。首先,我们将按升序对数组进行排序,然后对数组中的每个元素,我们将使用两个指针来检查和小于给定值的三元组。这样的三元组数量将是我们要跟踪的计数。
此外,我们将根据三元组的和是否小于或等于给定值来更新计数和指针。通过这种方式,我们可以有效地以O(n^2)的时间复杂度解决问题。这是一个非常有用的技术,可以在以后需要找到某些满足特定条件的组合的计数的问题中使用。
最后,我们将返回小于给定值的这样的三元组的计数。
方法
- 首先,按升序对给定的数字数组进行排序。
-
初始化三个变量:left、right和count。
-
然后使用两个指针的方法,左指针从0开始,右指针从结尾开始。
-
对于每次迭代,计算当前三元组的和(左指针指向的元素+右指针指向的元素+当前元素)。
-
如果和小于给定值,则增加计数和左指针。
-
如果和大于给定值,则减少右指针。重复此过程,直到左指针小于右指针。
示例
下面是一个完整的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 的三元组的数量。
-
使用 sort 函数对 arr 进行升序排序。
-
外部循环 for (let i = 0; i < arr.length – 2; i++) ** 遍历数组,同时初始化 **left 和 right 指针分别为 i 的下一个索引和数组的最后一个索引。
-
循环 while (left < right) ** 一直进行,直到 **left 指针大于或等于 right 指针。
-
再次说明,循环 **while (left < right) ** 一直进行,直到 left 指针大于或等于 right 指针。
-
在每次循环迭代中,计算 arr[i], arr[left] 和 arr[right] 的和。如果这个和大于或等于 sum ,则将 right 指针减一。如果和小于 sum ,则将 count 增加到 left 和 right 指针之间剩余元素的数量,并将 left 指针增加一。
-
函数返回 count 变量,它表示小于 sum 的三元组的数量。