兩數之和與多數之和：從 O(n²) 到 O(n) 的多維度解法

問題描述

給定整數數組和目標值 sum，找出兩個數使其和等於 sum。若多對滿足，任輸出一對。要求 O(n) 時間。
例：[1,2,4,7,11,15], sum=15 → 4, 11。

五種方案演進

1. 暴力雙循環 O(n²)

最直觀，面試必會但必不滿意。

2. 排序 + 二分查找 O(n log n)

排序後，對每個 a[i] 二分查找 sum - a[i]。無序數組同樣適用。

3. 哈希表 / 位圖 O(n) 時間、O(n) 空間

掃描數組，將 sum - a[i] 存入哈希表，或用位圖標記（數值範圍小時）。查找 O(1)。

4. 雙指針兩端掃描 O(n) 時間、O(1) 空間 —— 最優（前提：數組有序）

核心邏輯：i=0, j=n-1
- a[i]+a[j] > sum → j--（需減小和）
- a[i]+a[j] < sum → i++（需增大和）
- 相等 → 找到

bool findPairSorted(int a[], int n, int sum, int &x, int &y) {
    int i = 0, j = n - 1;
    while (i < j) {
        int s = a[i] + a[j];
        if (s == sum) { x = a[i]; y = a[j]; return true; }
        else if (s > sum) --j;
        else ++i;
    }
    return false;
}

5. 無序數組怎麼辦？

結論：無序時無法同時達到 O(n) 時間和 O(1) 空間，必須權衡。

擴展問題

Q1：同時返回兩數的原始下標？

哈希表存 value → index；排序方案需保存原下標（結構體/ pair）。

Q2：尋找 k 個數之和（k-Sum）？

• k=3：排序 + 固定一個 + 雙指針 O(n²)
• k=4：兩兩和存哈希表 O(n²) 空間，或排序 + 遞歸降維
• 通用：遞歸降維至 2-Sum，或 Meet-in-the-Middle（k 較大時）

Q3：數組有重複元素，找所有不重複對？

雙指針去重：找到後 while(i<j && a[i]==a[i+1]) i++; 同理 j--。

代碼：無序數組哈希表版（返回下標）

vector<int> twoSum(const vector<int> &nums, int target) {
    unordered_map<int, int> pos; // value -> index
    for (int i = 0; i < nums.size(); ++i) {
        int need = target - nums[i];
        if (pos.count(need)) return {pos[need], i};
        pos[nums[i]] = i;
    }
    return {};
}

總結

「兩數之和」是算法面試的Hello World，但其背後蘊含有序性利用、空間換時間、雙指針技巧、擴展到 k-Sum等核心思想。掌握各方案優劣與適用邊界，才是真正的內功。