1. Two Sum

leetcode網址

問題

在陣列中找到兩個數加總起來等於target，返回這兩個數的index

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
        Because nums[0] + nums[1] == 9, we return [0, 1].

Idea

因為要linear time，所以兩個for loop不行，這裡就需要hash map來當作額外儲存空間，因為hash map中搜尋元素的時間是O(N)

1. 跌代整個陣列
2. 每遇到一個數字nums[i]就檢查map中有沒有target-nums[i]
   • 有的話就回傳這兩個數的index: i, map[target-nums[i]]
   • 沒有的話就將此數存進map: map[nums[i]] = i
3. 直到結束

Solution

時間複雜度=O(N)；空間複雜度=O(N)

vector<int>twoSum(vector<int>nums, target){
    unordered_map<int,int>map;
    
    for(int i=0; i<nums.size(); i++){
        if(map.count(target-nums[i])){
            return {i, map[target-nums[i]]};
        }
        map[nums[i]]=i;
    }
    return {};
}