題目描述

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

• 每個輸入只對應一個答案。
• 同一個元素不能重復使用。
• 你可以按任意順序返回答案。

示例

輸入：

nums = [2, 7, 11, 15], target = 9

輸出：

[0, 1]

解釋： 因為 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]。

---

解題思路概覽

我們來介紹三種方法：

方法	思路	時間復雜度	空間復雜度
暴力法	雙重遍歷數組所有可能組合	O(n2)	O(1)
哈希表法（count 寫法）	邊遍歷邊用哈希查“補數”	O(n)	O(n)
哈希表法（find 寫法）	使用 find() + insert 更規范	O(n)	O(n)

方法一：暴力法（Brute Force）

思路：

使用兩層循環，枚舉數組中所有不同的兩元素組合，判斷是否滿足 nums[i] + nums[j] == target。

代碼：

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

分析：

• ? 思路直觀，適合入門；
• ? 時間復雜度高，不適合大數據量。

方法二：哈希表寫法（使用 count()）

思路：

• 用一個哈希表 map 存儲遍歷過的數字及其索引；
• 每次遍歷當前元素 nums[i] 時，判斷 target - nums[i]（即“補數”）是否已經存在于 map 中；
• 若存在 → 直接返回兩個下標；
• 若不存在 → 把當前元素加入 map。

代碼：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> map;  // key: 數值, value: 下標for (int i = 0; i < nums.size(); ++i) {if (map.count(target - nums[i])) {return {map[target - nums[i]], i};}map[nums[i]] = i;  // 記錄當前值及其下標}return {};}
};

分析：

• ? 查找和插入都為 O(1)；
• ? 非常適合刷題；
• ? 使用 map[key] 有可能在其他題中產生意外插入。

方法三：哈希表寫法（使用 find() + insert）

思路：

與方法二相同，但使用 STL 更推薦的方式：

• 用 find() 查找 key 是否存在；
• 用 insert() 插入新元素，避免不小心覆蓋已有值；
• 更規范、安全，適合用于工程開發或面試展示 STL 掌握能力。

代碼：

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> map;for (int i = 0; i < nums.size(); ++i) {auto iter = map.find(target - nums[i]);  // 查找補數if (iter != map.end()) {return {iter->second, i};  // 返回補數的下標和當前下標}map.insert({nums[i], i});  // 插入當前值}return {};}
};

分析：

• ? 與方法二效果相同；
• ? 代碼風格更符合 STL 正統寫法；
• 🟡 稍微冗長，適合工程/面試環境。

---

總結對比表

方法	時間復雜度	空間復雜度	是否易懂	是否規范	是否適合面試
暴力枚舉	O(n2)	O(1)	? 簡單	?	? 太慢
哈希法（count）	O(n)	O(n)	? 簡潔	🟡 有插入副作用	? 快速刷題
哈希法（find）	O(n)	O(n)	🟡 略長	? 安全規范	? 面試優選

---

一句話總結：

“用哈希表存已經看過的數，找當前數的補數是否在哈希表中” 是兩數之和的核心思路，掌握后可以一鍵通關各類“求和組合”題！