題目描述

給定一個整數數組 numbers 和一個目標值 target，請在數組中找到兩個數字，使它們的和等於 target。函數 twoSum 需返回這兩個數字的索引（index1 < index2），注意索引從 1 開始計算。題目保證每組輸入恰好存在一組解。

範例：

輸入: numbers = {2, 7, 11, 15}, target = 9
輸出: index1 = 1, index2 = 2

初步嘗試：暴力雙重循環

看到題目標記為 Medium，直覺上最直接的解法是雙重遍歷：外層循環固定第一個數，內層從後向前尋找第二個數。代碼寫起來很順手：

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        vector index;
        for (int i = 0; i < numbers.size(); ++i) {
            for (int j = numbers.size() - 1; j > i; --j) {
                if (numbers[i] + numbers[j] == target) {
                    index.push_back(i + 1);
                    index.push_back(j + 1);
                    break;
                }
            }
        }
        return index;
    }
};

提交後卻收到 Time Limit Exceeded。O(n²) 的複雜度在大數據下徹底失效，必須優化。

關鍵突破：哈希表將查找降為 O(1)

重新審題：如何避免重複循環？哈希表天生具備 O(1) 平均查找複雜度，正好解決「已知一數，快速查找另一數是否存在」的問題。遍歷數組時，將當前數值存入哈希表，同時檢查 target - 當前值 是否已在表中。

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        vector index;
        unordered_map hashMap;  // value -> index (1-based)
        for (unsigned int i = 0; i < numbers.size(); ++i) {
            int complement = target - numbers[i];
            if (hashMap.find(complement) != hashMap.end()) {
                index.push_back(hashMap[complement]);
                index.push_back(i + 1);
                break;
            }
            hashMap[numbers[i]] = i + 1;
        }
        return index;
    }
};

時間複雜度從 O(n²) 降至 O(n)，空間複雜度 O(n)，順利 AC。

測試主函數

方便本地驗證，附上 main 函數（LeetCode 提交時僅需 Solution 類）：

int main() {
    Solution s;
    int arr[3] = {3, 2, 4};
    int target = 6;
    vector numbers(arr, arr + 3);
    vector index = s.twoSum(numbers, target);
    cout << "index1=" << index[0] << ", index2=" << index[1] << endl;
    return 0;
}

心得總結

這道題是演算法入門的經典教案：暴力解法雖直觀但效率低；哈希表以空間換時間，將查找從線性降為常數，是解決「兩數之和」類問題的核心思路。初學者易陷入「雙重循環」的舒適區，實戰中必須訓練「預存與查找」的哈希思維。