問題描述

給定整數數組和目標值 Sum，找出數組中和為 Sum 的兩個數。假設至少存在一組解。

方案對比

方案一：暴力枚舉

void findPairBrute(const std::vector<int>& a, int target, int& x, int& y) {
    for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = i+1; j < a.size(); ++j)
            if (a[i] + a[j] == target) { x = a[i]; y = a[j]; return; }
}

方案二：排序 + 二分查找

void findPairBinarySearch(std::vector<int> a, int target, int& x, int& y) {
    std::sort(a.begin(), a.end());
    for (size_t i = 0; i < a.size(); ++i) {
        int need = target - a[i];
        if (std::binary_search(a.begin() + i + 1, a.end(), need)) {
            x = a[i]; y = need; return;
        }
    }
}

方案三：哈希表（單遍歷）

void findPairHash(const std::vector<int>& a, int target, int& x, int& y) {
    std::unordered_set<int> seen;
    for (int v : a) {
        int need = target - v;
        if (seen.count(need)) { x = need; y = v; return; }
        seen.insert(v);
    }
}

⚠️ 若數組含重複元素且目標為 2×v，需用 unordered_map<int, int> 計數或檢查索引。

方案四：排序 + 雙指針（推薦通用）

void findPairTwoPointers(std::vector<int> a, int target, int& x, int& y) {
    std::sort(a.begin(), a.end());
    size_t i = 0, j = a.size() - 1;
    while (i < j) {
        int sum = a[i] + a[j];
        if (sum == target) { x = a[i]; y = a[j]; return; }
        else if (sum < target) ++i;
        else --j;
    }
}

原理：有序數組兩端向中間收斂，和偏小移動左指針增大和，偏大移動右指針減小和。單次遍歷 O(n)，總複雜度由排序決定。

擴展：返回所有不重複數對

std::vector<std::pair<int,int>> findAllPairs(std::vector<int> a, int target) {
    std::sort(a.begin(), a.end());
    std::vector<std::pair<int,int>> ans;
    size_t i = 0, j = a.size() - 1;
    while (i < j) {
        int sum = a[i] + a[j];
        if (sum == target) {
            ans.emplace_back(a[i], a[j]);
            int lv = a[i], rv = a[j];
            while (i < j && a[i] == lv) ++i;
            while (i < j && a[j] == rv) --j;
        } else if (sum < target) ++i;
        else --j;
    }
    return ans;
}

工程選型建議

• **數據量小 / 簡單場景** → 方案四（代碼簡潔、無額外空間、穩定 O(n log n)）
• **極大數據 / 多次查詢** → 方案三預建哈希表，單次查詢 O(n)
• **不可修改原數組** → 方案三或拷貝後方案四
• **需要索引而非值** → 方案三存儲 value→index 映射