雙指針演算法概念

"雙指針"是一種在數組或鏈表中使用兩個指針來進行操作的技術。這兩個指針通常被稱為“快”指針和“慢”指針，或者“左”指針和“右”指針，根據其在數據結構中的移動速度或位置來命名。
雙指針演算法在處理數組或鏈表的問題中非常有效，可以幫助我們以更優的時間複雜度解決問題。常見的應用包括兩數之和、判斷鏈表是否存在環、找到鏈表的中間節點等。
雙指針可以分為以下幾種類型：

同向雙指針：兩個指針都從同一側開始移動，直到其中一個或兩個達到終點。這種策略可以用來解決例如“移除元素”、“最大連續子序列和”等問題。
相向雙指針：兩個指針分別從兩側開始，向中間靠攏，直到兩個指針相遇。這種策略可以用來解決例如“兩數之和”、“迴文字元串判斷”等問題。
快慢雙指針：兩個指針以不同速度移動，快指針移動的速度是慢指針的兩倍。這種策略常用來解決例如“是否存在環”、“找到中間節點”等問題。

無論使用哪種類型的雙指針，關鍵都在於設定好指針移動的規則，從而減少不必要的計算和遍歷，提升演算法效率。

雙指針演算法在 C++ 中是一種常見的演算法優化策略。如其名，這意味著在演算法中，我們使用兩個同類型的指針，通常是在一個數組或鏈表中。

這種方法主要用於序列或鏈表的遍歷，可以減少時間複雜度，降低問題的複雜性。常見的使用情況有逆序數組，找到數組中的兩數之和等問題。

下麵我將展示一個代碼示例，題目是在排序數組中找出兩個數，使它們的和等於目標數。這是一個典型的雙指針演算法的使用場景。

#include<bits/stdc++.h>
using namespace std;

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        if (numbers[left] + numbers[right] == target) {
            return {left + 1, right + 1};
        } else if (numbers[left] + numbers[right] < target) {
            ++left;
        } else {
            --right;
        }
    }
    return {-1, -1};
}

int main() {
    vector<int> numbers = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(numbers, target);
    cout << "Index1: " << result[0] << ", Index2: " << result[1] << endl;
    return 0;
}

在上述代碼中，我們使用雙指針技術，左指針從數組起始位置開始，右指針從數組最後位置開始，因為給出的數組是排序好的，所以如果兩個指針指向的兩數之和小於目標數，那麼左指針右移；如果兩數之和大於目標數，那麼右指針左移，如此迴圈直到找到符合條件的兩數。