LeetCode 1. Two Sum 詳解

題目：給定整數陣列 nums 與目標值 target，找出兩個數使其和等於 target，返回其下標（1-based），且 index1 < index2。假設每組輸入僅有一解，同一元素不可重複使用。

範例：nums = [2,7,11,15], target = 9 → 輸出 [1,2]（因為 2+7=9）。

解法一：排序 + 雙指針 — O(n log n)

思路：複製陣列並排序，雙指針 left、right 從兩端向中間收斂。若和過小則 left++，過大則 right--，相等則找到目標值對。最後在原陣列中查找這兩個值的原始下標（注意處理重複值）。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        int l = 0, r = sorted.size() - 1;
        while (l < r) {
            int sum = sorted[l] + sorted[r];
            if (sum == target) break;
            else if (sum < target) ++l;
            else --r;
        }
        // 在原陣列中找下標
        vector<int> ans;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == sorted[l] || nums[i] == sorted[r]) {
                ans.push_back(i + 1); // 1-based
                if (ans.size() == 2) break;
            }
        }
        return ans;
    }
};

優點：空間 O(1)（不計輸出），思路直觀。
缺點：排序破壞原始順序，需額外掃描找下標；存在重複值時需小心處理（如 [3,3], target=6）。

解法二：哈希表單次掃描 — O(n) 時間，O(n) 空間 ⭐ 推薦

思路：遍歷陣列，對於當前元素 x，檢查 target - x 是否已存在於哈希表中。若存在，直接返回兩者下標；否則將 x 及其下標存入表中。因為是單次遍歷，自然保證先找到的下標較小。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp; // 值 -> 下標 (0-based)
        for (int i = 0; i < nums.size(); ++i) {
            int need = target - nums[i];
            if (mp.count(need)) {
                return {mp[need] + 1, i + 1}; // 轉 1-based
            }
            mp[nums[i]] = i;
        }
        return {}; // 題目保證有解，不會執行到這
    }
};

關鍵細節：先查後存，避免將自己配對給自己（如 target=6, nums=[3] 時不會誤判）。

複雜度對比

延伸變體

• Two Sum II - Input Array Is Sorted (LeetCode 167)：陣列已排序，直接雙指針 O(n) O(1)。
• Two Sum III - Data structure design (LeetCode 170)：設計支援 add 與 find 的資料結構，哈希表計數即可。
• 3Sum / 4Sum：固定一/兩個數，轉化為 Two Sum 子問題。

總結

Two Sum 是演示「空間換時間」與「哈希表查找」的教科書級題目。實際工程中，面對大規模數據查找配對問題，哈希表（或資料庫索引）幾乎是唯一可行方案。掌握其邊界條件處理（重複值、自我配對），是演算法基本功的重要體現。