兩個指針技巧的JavaScript程序

JavaScript程式的雙重指標技術是一種常用的演算法方法，用於解決需要線性時間複雜度的各種問題。這種技術廣泛用於查找、排序或操作數組、字串或鍊錶的問題的解決方案。這個方法透過維護兩個指針，一個從資料結構的開頭開始，另一個從結尾開始，然後透過它們相向迭代，直到找到解決方案。

在本教學中，我們將探討雙指標技術的概念以及如何使用JavaScript程式語言來實現它。所以讓我們先從問題陳述開始，然後在這個有趣的教程中繼續前進！

問題陳述

給定一個按升序排序的陣列 A，包含 N 個整數，檢查是否存在任何一對元素 (A[i], A[j])，使得它們的和等於 X。

現在讓我們透過一些例子來理解上述程序的作用。

Input: const array = [1, 3, 5, 7, 9];
   const X = 12;
Output: Pair found at indices 1 and 4

解釋 − 在這種情況下，輸入數組中的元素對（3，9）相加得到目標和12，程式正確地辨識出索引為1和4的元素對。

Input: const array = [1, 3, 5, 7, 9];
   const X = 9;
Output: Pair not found

Explanation − 在這種情況下，如果目標和為9，則不存在這樣的一對，函數應該傳回「pair not found」。

演算法

使用雙指標技巧的演算法來尋找排序數組中是否存在一對元素，它們的和等於給定的目標值 -

• 初始化兩個指針，left = 0，right = 數組長度 - 1。

• 當左邊小於右邊時，執行下列動作

  • 計算索引為left和right處元素的和。

  • 如果總和等於目標值，則傳回左索引和右索引。

  • 如果總和小於目標值，則增加左邊。

  • 如果總和大於目標值，則減少右側。

• 如果不存在這樣的一對，回傳null。

上述演算法使用雙指標技術在已排序的陣列中搜尋一對元素，使它們的和等於給定的目標值。指標從陣列的兩端開始，並根據指標處元素的和與目標值的比較向彼此靠近。如果和小於目標值，則將左指針向右移動以增加和。如果和大於目標值，則將右指標向左移動以減少和。如果和等於目標值，則程式傳回這對元素的索引。如果不存在這樣的一對元素，則程式傳回未找到一對。

現在讓我們透過一個例子來理解這個演算法，在這個例子中，我們將使用JavaScript來實作先前討論過的問題陳述。

Example

的中文翻譯為：

範例

In this program, we used the Two Pointers Technique to find whether there exists a pair of elements in a given sorted array whose sum equals a given target. By iterating through the array and moving the pointers base on the pointers sum 問題at the pointers, the program efficiently finds the pair of elements (if it exists) in O(N) time complexity, where N is the number of elements in the array.

function findSumPair(array, X) {
   let left = 0;
   let right = array.length - 1;
   while (left < right) {
      const sum = array[left] + array[right];
      if (sum === X) {
         console.log(`Pair found at indices ${left} and ${right}`);
         return [left, right];
      } else if (sum < X) {
         left++;
      } else {
         right--;
      }
   }
   console.log('Pair not found');
   return null;
}
const array = [1, 3, 5, 7, 9];
const X = 12;
console.log(`Array: ${array}`);
console.log(`Target sum: ${X}`);
findSumPair(array, X);

結論

在本教程中，我們探討了雙指標技術的概念以及如何使用JavaScript程式語言來實現它，以解決涉及在排序數組中搜尋或比較一對元素的問題。我們還學習了使用雙指標技術來找到一對元素，使其和等於給定目標的演算法。透過使用這種技術，我們可以顯著提高程式在時間複雜度方面的效率。具體而言，雙指標技術可以在O(N)的時間複雜度內解決這類問題，這比O(N^2)的暴力方法快得多。因此，學習並應用這種技術以有效率地解決類似問題是非常重要的。

以上是兩個指針技巧的JavaScript程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！