題目連結(https://leetcode.com/problems/two-sum/description/)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

＊Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

因爲此題是 sum 類題目基礎，而我對 unordered_map 以及雜湊表概念較為不熟，故選擇這題分享。

1. Repeat（題目重複確認）

• 輸入：一個整數陣列 nums 和目標數字 target。
• 輸出：返回陣列中 兩個數字的索引，使它們相加等於 target。
• 前提：每個輸入只會有一個解，不可使用同一個元素兩次。

2. Examples（舉例確認理解）

如果陣列 nums 中有任兩個數相加等於目標值，就返回兩個數字的索引，比如說2+7＝9，返回的並不是數字本身，而是數字對應的索引，第0、1位。而不能用同一個元素兩次，即使偶數目標值可以用兩個相同元素表達，但要有兩個相同元素使用。

nums = [2, 7, 11, 15], target = 9
-> 2 + 7 = 9
-> return [0, 1]

nums = [3,3], target = 6
-> return [0,1]

3. Approach（解題思路）

方法 1：暴力法

• 最直接的做法是列出所有配對組，用兩層迴圈，枚舉每一對數字，看它們和是否等於 target。
• 時間複雜度：O(n²)
• 空間複雜度：O(1) 沒有額外空間，單純用整數變數運算
• 適合小陣列，但大陣列會超時。

方法 2：Hash Map（雜湊表）

• 給定一個重要變數：餘數，遍歷 nums 陣列，用目標值減去每一個數，並檢查 target - num 是否已經在雜湊表中：

  • 如果有，表示找到可配對該數字使其為目標值的數，返回索引。
  • 如果沒有，把此數和它的索引放進雜湊表，繼續下一輪。

• 時間複雜度：O(n)

• 空間複雜度：O(n)多設定一個有 n 個元素的 map(有key和value)

4. Code（C++）

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++){ //j從i+1開始才不會重復使用到同一個元素
				int solution = nums[i] + nums[j];
				if(target == solution)
					return {i, j};
			}
		}
		return {};
	}
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;  // key:數字, value:索引
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];  // 差值（餘數）
            if (mp.count(complement)) {        // 如果差值已經出現過
                return {mp[complement], i};    // 返回差值索引與當前索引
            }
            mp[nums[i]] = i;  // 儲存當前數字及索引
        }
        return {};  // 理論上不會到這裡，因為題目保證一定有解
    }
};

5. Test 測試

輸入：

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

1. i = 0, num = 2
   • complement = 9 - 2 = 7
   • mp 還沒有 7 → 存 2 的索引: mp = {2:0}
2. i = 1, num = 7
   • complement = 9 - 7 = 2
   • mp 有 2 → 找到解，回傳索引值{0,1}
   • return {0,1}

輸入：

nums = [3, 3], target = 6

1. i = 0, num = 3
   • complement = 3
   • mp 沒有 → 存 3 的索引: mp = {3:0}
2. i = 1, num = 3
   • complement = 3
   • mp 有 3 → 找到解 {0,1}
   • return {0,1}

6. 相關題目與延伸概念

• LeetCode 167. Two Sum II：已排序陣列，要求使用雙指針
• LeetCode 15. 3Sum：找三個數字加總為零
• LeetCode 18. 4Sum：找四個數字加總為目標
• 延伸概念：
  • 雜湊表快速查找
  • 雙指針技巧
  • 空間換時間策略

7. 補充：語法＆注意事項

① unordered_map<int,int> mp;

• unordered_map<key_type, value_type> name 要宣告兩個型別及 map 的名稱
  • key_type = map 的 key，這裡是陣列中的數字（int）
  • value_type = key 對應的值，這裡是索引（int）

② mp.count(complement)

• 用來檢查 map 中是否存在某個 key。
• 存在會返回 1 ，不存在返回 0。

③ mp[nums[i]] = i;

• 將數字 nums[i] 和它的索引 i 存進 map。
• 注意順序：
  • 先檢查 complement → 沒有的話再存 nums[i]
  • 如果順序反過來，可能會把自己配對自己，造成錯誤。

④ return {mp[complement], i};

• C++11 的寫法，用大括號 {} 建立一個 vector<int> 返回。
• 不要用逗號（return mp[complement], i;）
  • 逗號運算子會只返回最後一個值 → 會出錯。

1. 不要把自己當作 complement
   • 所以要先檢查 complement，再存當前數字。
2. 返回值一定要是 vector
   • return {mp[complement], i};
   • 不能寫成 return mp[complement], i; 或 return i, mp[complement];
3. 題目保證有解
   • 所以不需要額外檢查 return {}，只是防止編譯報錯。

ps. 部分內容經 AI 協助整理