今天來稍微改變一下 Two Sum 這題題目
原本的題目要回傳nums中的index，我們來把他改成回傳原數吧！

題目：
給一個元素皆不同的陣列以及目標的總和，寫一個函式回傳陣列，內含兩個數總和恰為目標數，且兩數不可以同一個元素，答案順序可和原本陣列不同，可以假設最多只有一組解，若沒有找到任何解則回傳空陣列

廢話不多說直接來個大家一定會用的暴力解！也就是檢查每個已知的元素，依序檢查，把目標總和減去當下被檢查的數，往後依序檢查

時間複雜度：Ｏ(n^2)
空間複雜度：Ｏ(1)

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

想辦法優化吧！

利用hashTable，雖然多花了Space-> Ｏ(n)
但是時間複雜度可以降到 Ｏ(n)

hashTable 可以讓我們在常數的時間Ｏ(1)來取得我們要的數
在javascript可以直接宣告一個{}來使用

舉個例子來說
Input：array = [3, 5, -4, 8, 11, 1, -1, 6],
target = 10

我們的目標總和為10
也就是x+y = 10

依序拜訪array
step1: 取出3，也就是把x設為３，則 y = 7

看看我們的hashTable是否有 7 ? 發現沒有，就把3當作key放到hashTable內，並把value設為true → 3: true, 依序做一樣的操作...
直到我們做到了-1，會發現目前hashTable如下

{ 3: True, 5:True, -4:True, 8:True, 11:True, 1:True}

y = 10 -(-1)=11

可以看到11在hashTable！
我們把[-1, 11]放到array 得到我們的答案

時間複雜度為O(n) ，n也就是input array的長度，因為我們只需要依序拜訪這個array一次，並計算y (constant time)，並且在hashTable中取得y也只用constant time

此外space也是O(N) → 看我們的hashTable就可以知道
有沒有明顯感受出和暴力法的差異?

function twoNumberSum(array, targetSum) {
  const hashTable = {};
  for (const x of array) {
    const y = targetSum - x;
    if (y in hashTable) {
      return [x, y];
    } else {
      hashTable[x] = true;
    }
  }
  return [];
}

除了這個方法外，還有另一個優於暴力法的方式。
就是先把array做sort（好的排序方式如Quick sort, Merge sort, Heap Sort）→ 花 O(nlogn)
排序好後就可以在O(n)的時間內找到目標總和，且不需要額外的空間來儲存 space O(1)

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

假設我們有一個左箭頭(left pointer)指到第一個element，right point指到最後一個element

把 -4 + 11 = 7
然後我們發現７< 10 (目標)

如果我們現在去移動右邊指標，被加的數就會變小了更不會接近10
所以我們應該移動left pointer
也就是 -1 + 11 (不小心得到答案了)

同理如果我們今天target = 1２那我們應該怎麼移動指標?
繼續移動左指標對吧？
1+11
那如果沒有找到的時候就是左右兩個指標相遇
其實LeetCode也有一道類似題: Two Sum II - Input array is sorted

Time : O(nlogn)+O(n) = O(nlogn)

function twoNumberSum(array, targetSum) {
  array.sort((a, b) => a - b);
  let leftPointer = 0;
  let rightPointer = array.length - 1;
  while (leftPointer < rightPointer) {
    const tmpSum = array[leftPointer] + array[rightPointer];
    if (tmpSum === targetSum) {
      return [array[leftPointer], array[rightPointer]];
    } else if (tmpSum < targetSum) {
      leftPointer++;
    } else {
      rightPointer--;
    }
  }
  return [];
}

相信看到這裡，原本的Two sum題目一定難不倒你，也別忘了自己試試喔！
其實後面用了左右指標先來看這題題目是為了先熟悉一下明天的題目

明日題目預告：3Sum