Two Sum

1. Two Sum

第一天的 leetcode 系列，先小試身手，從最簡單經典的 Two Sum 開始做做看。
之前就有解過這題，那次解完之後實在不知道還可以怎麼解比較好，於是就偷看了別人的答案。
沒想到還記得，所以稍微想了一下，測試完沒問題就直接 Submit 了。

最基礎解法：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
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]
    }
  }
};

沒什麼特別的，就是把 nums 直接雙層 for loop 過去。
但這個解法的時間複雜度是 $O(N^2)$

$O(N)$解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const hashTable = {}
  for (let i = 0; i < nums.length; i++) {
    if (hashTable.hasOwnProperty(nums[i])) return [i, hashTable[nums[i]]]
    hashTable[target - nums[i]] = i
  }
};

策略是，把 for loop 過的 element 所需要的對應數字記下來，當 loop 到那個數字的時候，就表示找到答案了。
例如：

Input: nums = [2, 5, 7, 11], target = 9

i = 0

nums[0] = 2
target - 2 = 7
把 7 跟這個 index 記錄起來

hashTable = {
  7: 0
}

i = 1

nums[1] = 5
找 hashTable 裡面有沒有 5 這個 key，沒找到，表示前面找過的數字沒有一個加 5 會等於 target 的。
target - 5 = 4
繼續加入 hashTable，此時 hashTable 長這樣：

hashTable = {
  7: 0,
  4: 1
}

i = 2

nums[2] = 7
找 hashTable 裡面有沒有 7 這個 key，有找到，表示前面第 0 個 element 可以跟他配對，所以答案是 [0, 2]