problem

輸入為一陣列及一整數 target，陣列不為空陣列，且元素不重複。如果陣列中有四個數字相加等於 target，以雙層陣列 (two-dimentional array) 的結構回傳所有數組 (順序不拘)，否則回傳空陣列。

sample input:
array = [7, 6, 4, -1, 1, 2]
target = 16

sample output:
[
 [7, 6, 4, -1],
 [7, 6, 1, 2]
]

開賽的時候寫了 two number sum 和 three number sum 問題，有很多有趣的解法，現在到了比賽最後，就以 four number sum 做結。

假設任意四個數字 x, y, z, k，如果將它們分為兩個一組，則四數總和可以想成兩組數字總和 (x + y) + (z + k)。也就是說如果找到陣列中所有的兩數字和，可以將這個問題簡化為 two number sum 的變化型。

two number sum 中有使用 hash table 的解法，過程中對於每個數字利用 (target - 數字) 進行查找，並將數字儲存。而這一題假設 x + y 為 P，z + k 為 Q，可以嘗試同樣的方法，查找 (target - P)，並記錄 Q，有找到符合的解再進一步記錄四個數字。不過相較於單純的 two number sum，還會需要考慮兩個問題：

1. 可能會有不同數字組合得出相同的 P/ Q
   例如 [7, 6, 4, -1, 1, 2] 中，4 + 2 和 7 + (-1) 都是 6，所以在 hash table 中可能需記成這種形式：
   {
    6: [[4, 2], [7, -1]]
   }
2. 要避免重複計算
   若 array = [7, 6, 4, -1, 1, 2]，target = 16
   hash table 中可能會記錄如下，這樣就會得出兩組相加為 16 的解，但其實是同樣的四個數字以不同方式排列，要避免這樣的情形。
   {
    13: [[7, 6]],
    3: [[4, -1]],
    10: [[6, 4]],
    6: [[7, -1]]
   }

綜合以上，具體的步驟是：

1. 迴圈過每個數字 i，對 i 進行以下步驟 2、3，
2. 以一個迴圈看 i 後面的所有數字 j，並計算 i + j == P。檢查（target - P） 是否有在 hash table 中，如果有，代表找到解，將所有組合推進結果陣列中。如果沒有，不將 P 加入，繼續看下個數字。
3. 以一個迴圈看 i 前面的所有數字 k，並計算 i + k == Q。檢查 Q 是否有在 hash table 中，如果有，將 [i, k] 的組合加入其中。如果沒有，新增 Q 及組合進去。
4. 最後回傳結果陣列。

統整一下：
步驟 2 只會檢查是否有解，不加入 hash table，
步驟 3 只會加入 hash table，不檢查是否找到解。

之所以在步驟 2 不加入 P，步驟 3 才加入 Q，是要在組合第二次出現時才加入 hash table，以此來避免重複。
例如 array = [7, 6, 4, -1, 1, 2]，target = 16
[7, 6] 這個組合，會在迴圈 i 為 6 的時候才記錄，就不會 7 和 6 的時候各記了一次。並且 [7, 6, 4, -1] 這組解會迴圈到 4 的時候才找到，不會在 i 為 7 和 6 的時候就反覆記錄。

n 為輸入陣列長度，
time: O(n^2) 這是大部分情況的時間，來自外層與內層的迴圈。可能會有的特殊情況是 hash table 中某個組合特別多 (如下)。碰到這種情況時，遍歷這些組合加入結果陣列就會花比較多時間，所以最遭情況的時間會不止 n^2 。
array = [-4, -3, -2, -1, 1, 2, 3, 4]，target = 0
hash = {
 0: [[-4, 4], [-3, 3], [-2, 2], [-1, 1]],
 ...
}
space: O(n^2) 因為會記錄 n^2 種數字和。

function fourNumberSum(array, target) {
  const results = [];
  const pairSums = {};
  for (let i = 0; i < array.length -1; i++) {
    for (let j = i + 1; j < array.length; j++) {
      const diff = target - (array[i] + array[j]);
      if (pairSums[diff]) {
        for (const pair of pairSums[diff]) {
          results.push([...pair, array[i], array[j]]);
        }
      }
    }
    for (let k = 0; k < i; k++) {
      const sum = array[i] + array[k];
      if (!pairSums[sum]) {
        pairSums[sum] = [[array[i], array[k]]];
      } else {
        pairSums[sum].push([array[i], array[k]]);
      }
    }
  }
  return results;
}

以上就是今年鐵人賽的最後一題。以這一題作為結尾，也很能表達這個月記錄演算法解題的心情，就是當碰到有點複雜又巧妙的方法時，其實常覺得一切只可意會，越多文字解釋反而越講不清楚。

但即便很難表達，這條路上還是有很多老師、同伴每日不斷嘗試用更簡潔明瞭的方法描述演算法，這和不斷優化演算法本身應該算是一樣的修練，對於他們的貢獻真心感謝。