# [LeetCode 1. Two Sum](https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/613/week-1-august-1st-august-7th/3836/)
### Daily challenge Aug 2, 2021 (EASY)

>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.

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

:::info
**Example 2:**
**Input:** nums = [3,2,4], target = 6
**Output:** [1,2]
:::

:::info
**Example 3:**
**Input:** nums = [3,3], target = 6
**Output:** [0,1]
:::

:::warning
**Constraints:**
* 2 <= nums.length <= 104
* -109 <= nums[i] <= 109
* -109 <= target <= 109
* Only one valid answer exists.
:::

---

### Approach 1 : Hash Map
**`4 ms ( 99.68% )`** **`O()`**

使用 **`unordered_map<int, int> list`** 儲存每個數字所在的 `index`。
> * 遍歷 `nums` 中所有元素，尋找 **`complement = target - nusm[i]`**。
> * 若 `list` 中不存在 `complement` ---> 存入 `list` 中。
>找到答案 ---> 回傳 **`{i, list[complement]}`**。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> list;
        vector<int> ans;
        
        for(int i=0; i<nums.size(); i++){
            int complement = target - nums[i];
            if(list.find(complement) != list.end() && list[complement] != i){
                ans.push_back(i);
                ans.push_back(list[complement]);
                break;
            }
            
            list[nums[i]] = i;
        }
        
        return ans;
    }
};