解決問題的模式

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

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

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

02. 多指標模式

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

範例問題

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

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 < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

時間複雜度 - 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 < 0, so move the left pointer right:

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

第 5 步：重複此過程
繼續移動指標並計算總和，直到它們相遇或找到一對。

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

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

總和為零，因此函數傳回 [-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 < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 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)。這種模式用途廣泛，可以應用於廣泛的問題，使其成為優化程式碼效能的重要策略。

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

以上是解決問題的模式的詳細內容。更多資訊請關注PHP中文網其他相關文章！