# 1.Two Sum <span class="tag" data-diff="easy" />
{%hackmd RN5D4nggQRO8wzNqxuvlNw %}

## 題目
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:**

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

## 思路

for(let i in nums){
    for(let j=0;j<i;j++) if(nums[j] == nums[i]) return [j, i];
    nums[i] = target - nums[i]
}

這題用了2層迴圈，外層迴圈目的是為了計算每個element與target的差值，代表所需要的另一個數，而內層的迴圈則是在找出此位置前是否有另一個位置所需要的數與當前位置相同，若有，則回傳兩者的位置。
這個演算法雖然只跑了140ms，但居然只贏過不到30%的人，於是憤而(?)在討論區找到了這麼一個解法:

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

他利用hashmap的方法，一邊將所需的數存入hashmap中，一邊在hash map中搜尋之前是否有需求，其實跟我的方法大同小異，不過如果假設javascript在object中的搜尋所需複雜度為$O(1)$，那麼此方法的時間複雜度可以從$O(n^2)$下降到$O(n)$，不過在runtime所花的時間上，依然只比過50%的人。