已排序陣列中構成等差數列的所有三元組的 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²) 的雙指標法。