演算法：判斷數組中是否存在兩數之和等於目標值

問題：給定整數數組與目標值，判斷是否存在兩個元素之和等於目標值。

方法一：排序雙指針（推薦）

數組排序後，左指針指向最小，右指針指向最大。根據 sum = a[left] + a[right] 與目標比較：

• sum == target：找到，輸出並返回。
• sum > target：右指針左移（減小和）。
• sum < target：左指針右移（增大和）。

時間 O(n log n)（排序），空間 O(1)。缺點：無法輸出所有滿足條件的數值對。

void findPairSorted(int a[], int n, int target) {
    sort(a, a + n);
    int l = 0, r = n - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) {
            cout << a[l] << ' ' << a[r] << endl;
            return;
        } else if (sum > target) --r;
        else ++l;
    }
    cout << "無" << endl;
}

方法二：暴力二維表記錄所有數值對

構建 n x n 矩陣 M[i][j] = a[i] + a[j]（利用對稱性只存 i < j）。遍歷矩陣找等於目標值的位置，可輸出所有數值對。時間 O(n²)，空間 O(n²)，僅適合小規模或需列舉所有解的場景。

void findAllPairs(int a[], int n, int target) {
    vector> M(n, vector(n));
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            M[i][j] = M[j][i] = a[i] + a[j];
    for (int i = 0; i < n; ++i)
        for (int j = i+1; j < n; ++j)
            if (M[i][j] == target)
                cout << a[i] << ' ' << a[j] << endl;
}

方法三：哈希集合（單次遍歷，最優）

遍歷數組，對每個 x 檢查 target - x 是否已在集合中。是則找到；否則將 x 加入集合。時間 O(n)，空間 O(n)，可輸出所有不重複數值對（需額外去重邏輯）。

總結

面試首選排序雙指針（無額外空間）或哈希集合（線性時間）。暴力矩陣法理解思路即可，實際工程極少用。