# 1. Two Sum

## 題目概要
給定一個陣列 nums 和一個正整數 target，找出 nums 陣列中的兩個數加起來和為 target，並返回這兩個值的索引值。

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

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

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

## 解題技巧

- 直接用雙層 for 暴力解或者用 Hash Map 都可以解。

## 程式碼

### 暴力解法

時間複雜度 O(n2)：

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

Runtime: 156 ms, Memory: 42MB

### HashMap
for 迴圈遍歷 nums，計算 target 和當前值的差值，在 map 中找有沒有這個值的紀錄，如果沒有就將當前值和索引存進 map 中繼續遍歷。**[map 的 key 為要尋找的值，value 存的是索引]**

時間複雜度 O(n)：

// 第一種寫法
var twoSum = function(nums, target) {
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];

        if (typeof map[diff] === 'number') {
            return [i, map[diff]];
        } else {
            map[nums[i]] = i;
        }
    }
};

// 第二種寫法
var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];

        if (map.has(diff)) {
            return [map.get(diff), i];
        } else {
            map.set(nums[i], i);
        }
    }
};