# 1. Two Sum

## 1.問題

* 給予一個整數的array, 回傳兩個數值的索引其相加的總和為指定的目標
* 你可以假設每個input只有一組答案, 而且不會使用到相同的元素兩次

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIOXct2D8GiGqm97Wvg%2F-LIOjmFqon7h6HSf_pVt%2F2018072613.jpg?alt=media\&token=7557b83b-7437-4498-8f1d-d1a7b3316d17)

## 2.想法

* 第一種想法是使用recursive + back tracking, 但是這會很花時間, 太多操作
* 第二種只需要花費O(N)的時間, 將數字儲存到unorder\_map中 (map的key是數值, value是索引), 並一邊在map中尋找target - 數值, 如果找到了就則把map的value, value都放到要回傳的vector中&#x20;

## 3.程式碼

* 第一種方法

```
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        vector<int> records;
        vector<bool> used(nums.size(), false);
        tryGetSum(nums, res, records, used, target, 0);
        return res;
    }
private:
    void tryGetSum(vector<int>& nums, vector<int>& res, vector<int>& records, vector<bool>& used, int target, int start) {
        if (records.size() == 2 && 
            (nums[records[0]] + nums[records[1]]) == target){
            res.push_back(records[0]);
            res.push_back(records[1]);
            used[records[0]] = true;
            used[records[1]] = true;
            return;
        } else if (records.size() == 2 && (nums[records[0]] + nums[records[1]]) != target){
            return;
        }
        for (int i = start; i < nums.size(); i++) {
            if (!used[i]) {
                used[i] = true;
                records.push_back(i);
                tryGetSum(nums, res, records, used, target, i + 1);
                records.pop_back();
                used[i] = false;
            }
        }
    }
};
```

* 第二種方法

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

## 4.Performance

* 第一種方法

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIOXct2D8GiGqm97Wvg%2F-LIOlCrrCToCWxhtj7eM%2F2018072615.jpg?alt=media\&token=5b5fa39a-f8b4-46e4-b9b4-1131ebab7ae8)

* 第二種方法

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIOXct2D8GiGqm97Wvg%2F-LIOksmVDJ4joJ_ThrLM%2F2018072614.jpg?alt=media\&token=a02c1b6d-2745-44bf-8cfc-8ae77a250614)
