歡迎回到我們關於現代軟體工程問題解決的部落格系列！

在第 1 部分中，我們探索了頻率計數器模式，這是一種透過有效計算元素頻率來優化演算法的強大技術。如果您錯過了它或想要快速回顧一下，請在繼續之前先查看一下。

在這一部分中，我們將深入研究另一個基本模式：多指標模式。在處理需要同時比較、搜尋或遍歷多個元素的場景時，這種模式非常有用。讓我們探討一下它的工作原理以及可以在哪裡應用它來提高程式碼效率。

02. 多指標模式

多指標模式是演算法設計中使用的技術，其中使用多個指標（或迭代器）來遍歷數組或鍊錶等資料結構。此模式不依賴單一指針或循環，而是使用兩個或多個指針，以不同的速度或從不同的起點移動資料。

範例問題

寫一個名為 sumZero 的函數，它接受 排序的整數陣列。此函數應找到總和為零的 第一對 。如果存在這樣的對，則傳回包含這兩個值的陣列；否則，傳回 undefined.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

基本解決方案

function sumZero(arr){
    for (let i = 0; i 



時間複雜度 - O(N^2)

使用多指標模式的解決方案

第 1 步：理解問題

我們需要在 **sorted 陣列中找到兩個加起來為零的數字。由於數組是有序的，我們可以利用這個順序更有效地找到解決方案。 

第2步：初始化兩個指標

設定兩個指標：一個 (left) 從陣列開頭開始，另一個 (right) 從陣列結尾開始。 

例子：



Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5




第 3 步：計算指針處值的總和

將左右指針處的值相加即可得到和



Sum = -4   5 = 1




第四步：將總和與零做比較

• 如果總和大於零： 將右指標向左移動一步，總和減少。

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• 如果總和小於零： 左指針向右移動一步，總和增加。

New Sum = -4   2 = -2
Sum is -2 



第 5 步：重複此過程

繼續移動指標並計算總和，直到它們相遇或找到一對。 



New Sum = -3   2 = -1
Sum is -1 



總和為零，因此函數傳回 [-2, 2]。 

如果循環完成而沒有找到這樣的一對，則回傳 undefined.

最終代碼



function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left  0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left  ;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}




筆記：

時間複雜度：O(n) – 此函數有效率且隨陣列大小線性縮放。 

空間複雜度：O(1) – 此函數使用最少量的額外記憶體。 

結論

多指標模式是一種強大的技術，用於解決涉及在排序資料結構中搜尋、比較或操作元素的問題。透過使用多個相互移動的指針，我們可以顯著提高演算法的效率，在許多情況下將時間複雜度從 O(n²) 降低到 O(n)。這種模式用途廣泛，可以應用於廣泛的問題，使其成為優化程式碼效能的重要策略。 

請繼續關注我們的下一篇文章，我們將深入探討滑動視窗模式解決另一個涉及動態資料段的問題的重要工具。這是一個非常有用的模式，可以幫助您輕鬆解決更複雜的挑戰！