# 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中 

## 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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jenhsuan.gitbook.io/algorithm/leetcode/1.-two-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.