1. Two Sum

Leetcode 連結

解法一

這題最簡單的方法就是用兩個 for loop 來遍歷所有的組合。當找到兩個數字相加等於 target 的時候就回傳兩個數字的 index。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            if (nums[i] + nums[j] == target){
                return {i, j};
            }
        }
    }
    return {-1, -1}; // didn't find any pair
}

time complexity: O(n^2)
space complextiy: O(1)

解法二

試想一下，當我們在 nums[i] 的時候，我們想要找的是什麼？
其實我們想知道在 nums[i] 之前， target - nums[i] 這個數字有在沒有出現過，而且出現過的話要能立刻知道這個數字的 index。

我們可以利用 hash map ，key = i, value = nums[i] 來存取數字跟 index 的關係。
也就是說，當我們在 nums[i] 的時候，我們去 hash map 裡面看說 target - nums[i] 有沒有出現過。出現過的話，那代表我們找到這樣的 pair，回傳這個組合的 index 即可。

這邊要注意的是，要先找 target - nums[i] 是否出現過，再把 mp[nums[i]] = i 加入 hash map 中，避免重複使用同一個數字。
例如 nums = [1, 1], target = 2，如果先把 key value pair {1, 0} 加入，則會直接回傳 {0, 0}，得到錯誤的解答。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    unordered_map<int, int> mp;
        for (int i = 0; i < n; i++){
            if (mp.find(target - nums[i]) != mp.end()){
                return {mp[target - nums[i]], i};
            } 
            mp[nums[i]] = i;
        }
    return {-1, -1}; // didn't find any pair
}

time complexity: O(n)
space complextiy: O(n)