一、題目描述

原題

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的那兩個整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案，並且你不能使用兩次相同的元素。

你可以按任意順序返回答案。

示例

示例 1：
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1]

示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]

約束條件

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只會存在一個有效答案

二、題目解析

核心問題拆解

思考方向

三、算法解答

算法一：暴力枚舉法

1. 算法原理描述

核心思想：窮舉所有可能的兩數組合，檢查它們的和是否等於目標值。

實現方式：

• 使用兩層循環
• 外層循環固定第一個數 nums[i]
• 內層循環遍歷其後的所有數 nums[j]（j > i）
• 檢查 nums[i] + nums[j] == target

2. 算法解答過程

以 nums = [2, 7, 11, 15], target = 9 為例：

返回 [0, 1]

3. 算法原理圖像解析

4. 算法代碼

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        
        // 外層循環：固定第一個數
        for (int i = 0; i < n - 1; i++) {
            // 內層循環：遍歷第一個數之後的所有數
            for (int j = i + 1; j < n; j++) {
                // 檢查兩數之和是否等於目標值
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        
        // 題目保證有解，這裏不會執行到
        return {};
    }
};

5. 複雜度分析

6. 使用範圍

算法二：哈希表法（一遍哈希）⭐ 最優解

1. 算法原理描述

核心思想：將「尋找兩數之和」轉化為「尋找差值」問題。

關鍵轉換：

nums[i] + nums[j] = target
         ↓ 轉化
nums[j] = target - nums[i]

實現方式：

• 使用哈希表存儲已遍歷過的元素及其下標
• 對於當前元素 nums[i]，計算 complement = target - nums[i]
• 在哈希表中查找 complement 是否存在
• 若存在，説明找到答案；若不存在，將當前元素加入哈希表

優勢：哈希表的查找時間複雜度為 O(1)，整體只需一次遍歷。

2. 算法解答過程

以 nums = [2, 7, 11, 15], target = 9 為例：

3. 算法原理圖像解析

哈希表狀態變化：

4. 算法代碼

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 哈希表：key = 數值，value = 下標
        unordered_map<int, int> hashMap;
        
        for (int i = 0; i < nums.size(); i++) {
            // 計算當前元素的"配對值"
            int complement = target - nums[i];
            
            // 在哈希表中查找配對值
            if (hashMap.find(complement) != hashMap.end()) {
                // 找到了！返回兩個下標
                return {hashMap[complement], i};
            }
            
            // 未找到，將當前元素存入哈希表
            hashMap[nums[i]] = i;
        }
        
        // 題目保證有解，這裏不會執行到
        return {};
    }
};

5. 代碼詳解

// 關鍵點解析：

// 1. 為什麼用 unordered_map 而不是 map？
//    - unordered_map 基於哈希表，查找/插入 O(1)
//    - map 基於紅黑樹，查找/插入 O(log n)

// 2. 為什麼先查找再存入？
//    - 避免同一元素被使用兩次
//    - 例如：nums = [3, 3], target = 6
//    - 第一個3存入後，第二個3能找到第一個3

// 3. hashMap.find() vs hashMap.count()
//    - find() 返回迭代器，未找到返回 end()
//    - count() 返回 0 或 1
//    - 兩種寫法都可以，find() 更常用

6. 複雜度分析

7. 使用範圍

算法三：排序 + 雙指針法（特殊場景）

⚠️ 注意：此方法會丟失原始下標，需要額外處理。僅適用於返回值而非下標的變體題目。

1. 算法原理描述

核心思想：利用有序數組的性質，使用雙指針從兩端向中間逼近。

實現方式：

1. 將數組排序
2. 設置左指針 left = 0，右指針 right = n-1
3. 計算 sum = nums[left] + nums[right]
   • 若 sum == target：找到答案
   • 若 sum < target：左指針右移（增大和）
   • 若 sum > target：右指針左移（減小和）

2. 算法解答過程

以 nums = [2, 7, 11, 15], target = 9 為例（已排序）：

3. 算法原理圖像解析

雙指針移動規則：

4. 算法代碼

// 方法：保留原始下標的雙指針解法
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 創建副本並排序，保留原始下標
        vector<pair<int, int>> numWithIndex;
        for (int i = 0; i < nums.size(); i++) {
            numWithIndex.push_back({nums[i], i});
        }
        sort(numWithIndex.begin(), numWithIndex.end());
        
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int sum = numWithIndex[left].first + numWithIndex[right].first;
            
            if (sum == target) {
                return {numWithIndex[left].second, numWithIndex[right].second};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return {};
    }
};

5. 複雜度分析

6. 使用範圍

四、三種算法對比

💡 面試建議

五、知識點總結

1. 涉及的數據結構

2. 涉及的算法思想

3. C++ 知識點

// 1. unordered_map 的使用
#include <unordered_map>
unordered_map<int, int> map;
map[key] = value;           // 插入
map.find(key);              // 查找，返回迭代器
map.count(key);             // 返回 0 或 1
map.end();                  // 結束迭代器

// 2. vector 的初始化返回
return {a, b};              // 直接返回初始化列表

// 3. pair 的使用
pair<int, int> p = {value, index};
p.first;                    // 第一個元素
p.second;                   // 第二個元素

六、做題模板

「兩數之和」類問題通用模板

/*
 * 兩數之和問題模板
 * 適用於：在數組中尋找滿足 nums[i] + nums[j] = target 的配對
 */
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Step 1: 創建哈希表
        // key: 數組元素值
        // value: 元素下標
        unordered_map<int, int> hashMap;
        
        // Step 2: 遍歷數組
        for (int i = 0; i < nums.size(); i++) {
            // Step 3: 計算配對值
            int complement = target - nums[i];
            
            // Step 4: 在哈希表中查找配對值
            if (hashMap.find(complement) != hashMap.end()) {
                // 找到配對，返回結果
                return {hashMap[complement], i};
            }
            
            // Step 5: 將當前元素加入哈希表
            hashMap[nums[i]] = i;
        }
        
        // Step 6: 未找到（題目保證有解時不會執行）
        return {};
    }
};

模板流程圖：

模板變體

變體1：返回所有配對

vector<vector<int>> twoSumAll(vector<int>& nums, int target) {
    unordered_map<int, vector<int>> hashMap;  // 存儲所有下標
    vector<vector<int>> result;
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (hashMap.count(complement)) {
            for (int j : hashMap[complement]) {
                result.push_back({j, i});
            }
        }
        hashMap[nums[i]].push_back(i);
    }
    return result;
}

變體2：有序數組（雙指針）

vector<int> twoSumSorted(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left, right};  // 注意：這裏返回的是下標
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {};
}

七、相關題目推薦

八、面試高頻問答

Q1: 為什麼哈希表法要先查找再存入？

答：為了避免同一元素被使用兩次。例如 nums = [3], target = 6，如果先存入再查找，會錯誤地返回 [0, 0]。

Q2: 如果有多個答案怎麼辦？

答：題目保證只有一個答案。若需返回所有答案，需要使用 unordered_map<int, vector<int>> 存儲所有下標。

Q3: 哈希表 vs 紅黑樹（map vs unordered_map）？

答：

• unordered_map：哈希表，查找 O(1)，無序
• map：紅黑樹，查找 O(log n)，有序

本題不需要有序，選擇 unordered_map 更優。

Q4: 時間複雜度 O(n) 是最優嗎？

答：是的。至少需要遍歷一次數組才能確定答案，O(n) 是下界。

九、一圖總結