# 1. Two Sum

### Leetcode

#### <https://leetcode.com/problems/two-sum>

### 題目

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*****&#x20;one solution**, and you may not use the *same* element twice.

You can return the answer in any order.

**Example 1:**

<pre><code><strong>Input: nums = [2,7,11,15], target = 9
</strong><strong>Output: [0,1]
</strong><strong>Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [3,2,4], target = 6
</strong><strong>Output: [1,2]
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [3,3], target = 6
</strong><strong>Output: [0,1]
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

雙層迴圈硬解

```javascript
var twoSum = function(nums, target) {
    for(let i=0; i<nums.length; i++) {
        for(let j=i+1; j<nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};
```

Runtime: 96 ms Beats 37.93% of users with JavaScript

Memory: 49.64 MB Beats 30.19% of users with JavaScript

* **方法二**

一層迴圈 + Hash Table

```javascript
var twoSum = function(nums, target) {
    const map = new Map();

    for(let i=0; i<nums.length; i++) {
        const value = nums[i];
        const hashKey = target - value;
        if (map.has(hashKey)) {
            return [map.get(hashKey), i];
        }
        map.set(value, i);
    }
};
```

Runtime: 56 ms Beats 81.99% of users with JavaScript

Memory: 51.86 MB Beats 6.83% of users with JavaScript

### 參考資料

<https://ithelp.ithome.com.tw/articles/10269246>
