雙指針法

2.1 雙指針法定義。

雙指針法 是一種用於解決不同數組和字符串問題的技術，使用兩個指針（索引），根據特定規則在數據中移動。這種方法可以有效地解決與查找滿足特定條件的元素對、子集相關的問題。

此方法假設使用兩個指針，通常初始化在數據結構的兩端，然後彼此靠近或根據特定規則移動。相比較於更簡單的辦法，雙指針法可以顯著減少算法的時間複雜度。

主要原則

1. 初始化兩個指針：指針可以設置在數組或字符串的開始和結束，或基於任務的不同索引。
2. 移動指針：指針根據特定規則移動（例如，兩個指針向中心移動，或一個指針向前移動，而另一個保持不動）。
3. 檢查條件：在每一步檢查條件，以確定指針的進一步移動或算法的完成。

時間複雜度：

O(n) — 大多數情況下，因為兩個指針在數組中各自或多次移動，但總計不超過 O(n) 次迭代。

對於某些問題，根據條件和指針初始位置，時間複雜度可能是 O(n log n) 或 O(n^2)，但這是罕見的。

雙指針法解決的問題示例：

2.2 查找數組中兩個數，其和等於給定的數。

問題:

解決方案:

初始化一個指針在數組的開始，另一個在結尾。檢查指針下元素的和：

• 如果和等於 target，返回索引。
• 如果和小於 target，將左指針右移。
• 如果和大於 target，將右指針左移。

時間複雜度: O(n).

Python 代碼示例：

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 判斷是否為回文

問題:

檢查字符串是否為回文。

解決方案:

初始化指針在字符串的開始和結尾。比較指針下的字符：

• 如果字符相等，將兩個指針彼此靠近。
• 如果字符不相等，字符串不是回文。

時間複雜度: O(n).

Python 代碼示例：

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 從排序數組中刪除重複項

問題:

從排序數組中刪除重複項。

解決方案:

使用兩個指針，一個用於當前結果數組的位置，另一個用於遍歷所有元素：

• 如果當前元素不等於前一個，將其寫入結果數組。

時間複雜度: O(n).

Python 代碼示例：

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index