Leetcode: https://leetcode.com/problems/two-sum/

[正文]

分析

最一開始想到的解法是把每個組合都跑過看看是不是等於 target，但是這樣時間複雜度是 $O(n^2)$;
分析後發現可以用空間換取時間，$a_i + b_i = target \Rightarrow a_i = target - b_i$，只要存下 $target - b_i$ 的結果，再拿去和原本的 a 陣列去比對有沒有一樣的元素，直接輸出 index 就是我們要的結果！

example

target = 9
         a = [ 2,  7, 11, 15] = A
target - b = [ 7,  2, -2, -6] = B

> A[0] == B[1], output: [0, 1]

但是找兩陣列有沒有相同元素的時間複雜度還是 $O(n^2)$，並沒有比較好，我們需要換一個資料結構。把 B 陣列的元素拿來當 hash 的 key, index 當 value, 這樣確認有沒有一樣的操作就可以降低到 $O(1)$，整體的時間複雜度還是 $O(n)$

example

target = 9
A = [ 2,  7, 11, 15]
B = { 7:0,  2:1, -2:2, -6:3 }

> B[A[0]] == 1 有值, output: [0, 1]

打算開始寫 code 的時候發現我先建構 hash B 出來，再去 check A，整體來說跑 $O(2n)$，其實可以一邊建構 hash B 一邊 check，省下一點常數時間，變成 $O(n)$，主要就是每讀進一個 A，就 check 一次，沒有就丟進 hash B 裡面。

假設答案是 A[i], A[j] 且 i < j，會先讀到 A[i]，check 不會過，因為 A[j] 還不在 hash B 裡面，讀到 A[j]，check 會過，因為 A[i] 已經在 hash B 裡面了，B[A[j]] = i;

Code

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  let hash = Object.create(null);

  for (let index = 0; index < nums.length; index++) {
    const num = nums[index];

    if (hash[num] != undefined) {
      return [hash[num], index];
    }
    hash[(target - num)] = index;
  }
};

關於 Object.create(null) 的部分有人問，可以看看這一篇的解釋详解Object.create(null);

羊毛 | 寫 Code 雜談

LeetCode with JS - 0001 Two Sum

[正文]

分析

Code