已排序数组中构成等差数列的所有三元组的 JavaScript 程序

---

等差数列 (AP) 是一种数列，其中两个连续元素之间的差始终相同。我们将使用三种方法打印已排序数组中构成等差数列的所有三元组：朴素方法、二分查找法和双指针法。

问题介绍

在这个问题中，我们得到一个已排序的数组，这意味着所有元素都是递增的。我们必须找到数组中的三个元素，它们构成一个等差数列。例如：

给定数组：1 5 2 4 3

从给定数组中，我们有两个三元组：1 2 3 和 5 4 3，因为相邻元素之间的差是相等的。此外，正如文中所写，我们只需要找到三元组，因此我们不会查找更长的序列。

让我们来看一下查找三元组的方法：

方法

朴素方法

在这种方法中，我们只是使用循环遍历数组，对于每次迭代，我们将运行另一个数组来查找大于当前索引的数字。然后，我们将再次在第一个嵌套数组内实现一个嵌套数组来查找可以构成等差数列的元素。让我们看看代码：

示例

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         for(var k = j+1; k < n; k++){
            if(arr[j] - arr[i] == arr[k] - arr[j]) {
               console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + arr[k]);
            }
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

上述代码的时间复杂度为 O(N³)，其中 N 是数组的大小。

上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

朴素方法的后续改进

在前面的方法中，当我们有两个元素时，我们可以找到第三个元素，因为我们有公差，所以为了查找第三个元素，我们可以使用二分查找而不是线性查找，从而降低上述代码的时间复杂度：

示例

// function for binary search 
var binarySearch = function (arr, x, start, end) {
   if (start > end) return false;
   var mid=Math.floor((start + end)/2);
   if (arr[mid]===x) return true;
   if(arr[mid] > x)
      return binarySearch(arr, x, start, mid-1);
   else
      return binarySearch(arr, x, mid+1, end);
}
// function to find all the tripletes 
function findAP(arr){
   var n = arr.length
   // traversing over the array
   for(var i = 0; i< n;i++){
      for(var j = i+1;j<n;j++){
         // third element will be
         var third = 2*arr[j]-arr[i];
         if(binarySearch(arr,third,j+1,n)){
            console.log("Triplet is: " + arr[i] + " " + arr[j] + " " + third);
         }
      }
   }
}
// defining the array and calling the function 
arr = [1, 5, 2, 4, 3]
findAP(arr)

上述代码的时间复杂度为 O(N³)，其中 N 是数组的大小。

上述代码的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

高效方法

在这种方法中，我们将使用两个指针来查找与当前位置具有相同差的元素。让我们看看代码：

示例

// function to find all the triplets 
function findAP(arr){
   var n = arr.length
   
   // traversing over the array
   for(var i = 1; i< n;i++)    {
      var bptr = i-1
      var fptr = i+1
      while(bptr >= 0 && fptr < n)        {
         if(arr[i] - arr[bptr] == arr[fptr] - arr[i]){
            console.log("Triplet is: " + arr[bptr] + " " + arr[i] + " " + arr[fptr]);
            bptr--;
            fptr++;
         }
         else if(arr[i] - arr[bptr] > arr[fptr] - arr[i]){
            fptr++;
         }
         else{
            bptr--;
         }
      }
   }
}

// defining the array and calling the function 
arr = [1, 4, 7, 10, 13, 16]
findAP(arr)

上述代码的时间复杂度为 O(N²) ，其中 N 是给定数组的大小，上述方法的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

注意 - 前两种方法对于已排序或未排序的任何类型的数组都是有效的，但最后一种方法仅适用于已排序的数组，如果数组未排序，我们可以将其排序，并且此方法仍然是所有方法中最好的。

结论

在本教程中，我们实现了一个 JavaScript 程序，用于打印给定已排序数组中构成等差数列的所有三元组。等差数列 (AP) 是一种数列，其中两个连续元素之间的差始终相同。我们已经看到了三种方法：时间复杂度为 O(N³) 的朴素方法，时间复杂度为 O(N²logN) 的二分查找法，以及时间复杂度为 O(N²) 的双指针法。