# LeetCode - 1. Two Sum
###### tags: `LeetCode` `Guide` `C++` `Easy`
> 原題連結: https://leetcode.com/problems/two-sum/

> Difficulty: <span style="color: green;">Easy</span>

## 題目說明
Given an array of integers, return **indices** of the two numbers such that they add up to a specific target.

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

## 範例測資
### Example 1.
#### Input:
> Given nums = [2, 7, 11, 15], target = 9,
#### Output:
> [0, 1].
#### Explanation:
> Because nums[0] + nums[1] = 2 + 7 = 9， so return [0, 1].

## 說明

身為整個題庫的第一題，這題就是小case啦。

題目會指定一個數字target，要在array中找到2個數，加起來正好等於target，並回傳他們的索引值。

## Code與解析
### 做法1. Brute Force <span style="font-size:5px; color:green;">[Accept]</span>
> Runtime: 260 ms > faster than 9.90%
> Memory: 9.1 MB > less than 99.73%

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++){
            for(int j = 0; j < nums.size(); j++){
                if(i != j && nums[i] + nums[j] == target) return {i, j};
            }
        }
        return {};
    }
};

簡單利用兩層的迴圈，把整個array中的值兩兩配對過一遍，直到找到符合的項目為止。
因為測資不挑，所以即使是效率較差的暴力法也能AC。

### 做法2. One-pass Hash <span style="font-size:5px; color:green;">[Accept]</span>
> Runtime: 8 ms > faster than 92.99%
> Memory: 10.1 MB > less than 50.95%

class Solution {
private:
    map<int, int> index;
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++){
            if(index.find(target - nums[i]) == index.end()){
                index[nums[i]] = i;
            }
            else{
                return {index[target - nums[i]], i};
            }
        }
        return {-1, -1};
    }
};

這個做法也不難，而且因為只要讀過一次array，所需時間不會太多。
做法是在讀取的同時，把"哪個數字在哪裡出現過"這件事給記下來，這樣之後需要的時候就不必再遍歷一次，直接到對應的index找就好了。
舉例來說，若題目為:
> Array: [2, 15, 7, 1]
> Target: 9

第一個會讀到的是2，那因為沒有先前的數字，所以理所當然的找不到9-2=7的對應值。
那這時我們就會把"2出現在index=0"這件事給記下來:

map<int, int> index;
index[2] = 0;

第二個會讀到的是15，同樣的，我們沒有找到9-15=-7的對應值，所以也要把15記下來:

index[15] = 1;

下一個會讀到7，這次我們會發現9-7=2已經被記錄過了，所以存取index[2]，就能得到我們要的答案了。