problem

輸入為一陣列及一整數 target，如果陣列中有兩個數字 a, b 相加等於 target，回傳陣列 [a, b] (或 [b, a]，順序都可以)，否則回傳空陣列。
可以預設輸入陣列不為空陣列，其中元素不重複，並且至多只會有一組數字相加等於 target。另外陣列中的數字不能重複使用，例如當 array = [1, 2, 3]，target = 6，[3, 3] 不為解。

sample input:
array = [3, 5, -4, 8, 11, 1, -1, 6]
target = 10

sample output:
[-1, 11]

solution 01

最基本的解法是利用兩層迴圈，將所有可能的數組都看過一遍。
例如 [3, 5, -4, 8, 11, 1, -1, 6]
先將 3 和它後面所有的數字依序相加看是否等於 target
再將 5 和它後面所有的數字依序相加看是否等於 target
...以此類推，直到找到解或看完所有組合，屬於直覺但比較慢的解法。

n 為陣列長度
time: O(n^2)
space: O(1)

function twoNumberSum(array, target) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] + array[j] === target) {
        return [array[i], array[j]];
      }
    }
  }
  return [];
}

solution 02

第二種解的想法是用一個 hash table (以 JS 來說使用物件) 來做紀錄，減少查找的時間。

具體步驟是，遍歷過陣列一次，檢查每個數字 num 和 target 的差值 (target - num) 是否有在 hash table 中。如果是，代表找到解，否則將 num 存進 hash table 中。

例如 [3, 5, -4, 8, 11, 1, -1, 6], 10 及物件 {}
第一個數字為 3，(10 - 3) 沒有在物件中，所以將 3 存進去，
第二個數字為 5，(10 - 5) 沒有在物件中，所以將 5 存進去，
...以此類推，直到看到 -1 時，物件會為以下狀態：

// true 可以為任意值，因為重點只是利用 key 來紀錄 '已看過' 的數字。
{
    '3': true,
    '5': true,
    '-4': true,
    '8': true,
    '11': true,
    '1': true,
}

從中可以檢查到 11 (10 - (-1)) 已經有在物件中，因此回傳 [-1, 11]。

若 n 為陣列長度，這種解法的時間和空間複雜度為：
time: O(n) 因為遍歷陣列一遍，而對每個元素只有進行常數時間的運算。
space: O(n) 因為要將陣列元素另外存進 hash table 中。

function twoNumberSum(array, target) {
  const cache = {};
  for (const num of array) {
    const match = target - num;   // 稍微整理增加可讀性
    if (match in cache) {
      return [num, match];
    } else {
      cache[num] = true;
    }
  }
  return [];
}

以上提供兩種解法，之前面試時就是被問到這題的變化型，另外在 leetcode 上也有各種版本，所以應該算是很常見的題目。明天會繼續寫這題另外一種想法，並延伸解進階一點的 three number sum 問題。