資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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
說明 - 在這種情況下，如果目標和為 9，則不存在這樣的對，並且函式應返回“未找到對”。
演算法
用於雙指標技巧程式的演算法，用於查詢已排序陣列中是否存在任何元素對，其和等於給定目標 -
初始化兩個指標，left = 0 和 right = 陣列長度 - 1。
當 left < right 時，執行以下操作
計算索引 left 和 right 處元素的和。
如果和等於目標，則返回索引 left 和 right。
如果和小於目標，則增加 left。
如果和大於目標，則減少 right。
如果不存在這樣的對，則返回 null。
上述演算法使用雙指標技巧在已排序陣列中搜索元素對，其和等於給定目標。指標從陣列的兩端開始，並根據指標處元素的和與目標的比較向彼此移動。如果和小於目標，則將左指標向右移動以增加和。如果和大於目標，則將右指標向左移動以減少和。如果和等於目標，則程式返回元素對的索引。如果不存在這樣的對，則程式返回“未找到對”。
現在讓我們用一個示例來理解此演算法，在該示例中，我們將使用 JavaScript 實現我們之前討論的問題陳述。
示例
在此程式中，我們使用雙指標技巧來查詢給定已排序陣列中是否存在元素對，其和等於給定目標。透過遍歷陣列並根據指標處元素的和移動指標，程式有效地找到元素對（如果存在）的時間複雜度為 O(N)，其中 N 是陣列中元素的數量。
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) 的蠻力方法快得多。因此，學習並應用此技巧來有效地解決類似問題至關重要。
2K+ 閱讀量
