# 1. Two Sum
[leetcode網址](https://leetcode.com/problems/two-sum/description/)
## 問題
在陣列中找到兩個數加總起來等於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 {};
}