[演算法] Two Sum

此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

問題描述

指定一個特定的數字，在以陣列的方式傳入許多數字（numArray），看看能否在這些數字中透過加法組合出這個特定的數字：

// return every pair of numbers from 'numArray' that adds up to the 'targetSum'
function twoSum (numArray, targetSum) { ... }

twoSum([1, 6, 4, 5, 3, 3], 7)
// [[6, 1], [3, 4]]

條件：

1. 輸出的結果必須是陣列中含有陣列（array of arrays），例如：[[6, 1], [3, 4]]
2. 任何在 numArrays 中的數字是不可以被重複使用（在原課程中是可以被重複使用）

演算法實做

我們先建立兩個陣列，分別用來儲存配對好的結果（pairs）還有待配對的數字（waitForPair）：

function twoSum(numArray, targetSum) {
  let pairs = [];
  let waitForPair = [];
  /* ... */
  return pairs;
}

接著我們透過 for...of 來疊代傳進來的陣列，將每個傳進來的數值，稱做 currNumber，而要找的數值 counterPart 就會是：

let counterPart = targetSum - currNum;

如果 currNumber 在 waitForPair 找不到對應的 counterPart，就把它放入 waitForPair 中；如果可以在 waitForPair 中找到對應的 counterPart，就把它放入 pairs 中。

另外因為我們不要重複使用元素，所以要把在 waitForPair 中的數值也刪除。

寫成程式碼就像這樣：

function twoSum(numArray, targetSum) {
  /* ... */
  for (let currNum of numArray) {
    let counterPart = targetSum - currNum;
    let counterPartIndex = waitForPair.indexOf(counterPart);

    // 如果有找到相對應的 counterPart
    if (waitForPair.indexOf(counterPart) !== -1) {
      // 把這個 counterPart 從原本的陣列中移除
      waitForPair.splice(counterPartIndex, 1);
      // 把這個 counterPart 加到 pairs 中
      pairs.push([currNum, counterPart]);
    } else {
      // 如果沒有找到 counterPart，則先把這個數字存到待配對中
      waitForPair.push(currNum);
    }
  }
  /* ... */
}

完整程式碼

function twoSum (numArray, targetSum) {
  let pairs = []
  let waitForPair = []
  for (let currNum of numArray) {
    let counterPart = targetSum - currNum
    let counterPartIndex = waitForPair.indexOf(counterPart)
    if (waitForPair.indexOf(counterPart) !== -1) {
      waitForPair.splice(counterPartIndex, 1)
      pairs.push([currNum, counterPart])
    } else {
      waitForPair.push(currNum)
    }
  }
  return pairs
}

console.log(twoSum([1, 6, 4, 5, 3, 3], 7))      // [ [ 6, 1 ], [ 3, 4 ] ]
console.log(twoSum([40, 11, 19, 17, -12], 28))  // [ [ 17, 11 ], [ -12, 40 ] ]

Algorithm: two sum @ repl.it

資料來源

• Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy