JavaScript 解法 LeetCode 01. Two Sum

刷題啦！著名又經典的 LeetCode 第一題

🕒 published on ー 2022. 2. 22.

Photo by Jerry Wang on Unsplash

Free Talk

我的刷題初體驗，就是 Two Sum ，相信很多人也跟我一樣吧！

第一次看到題目的時候，抱歉…無任何 CS 背景、無任何相關工作經驗、不是天才又是純文組、當時初學 JS 才 3 個月的我，真的不知道該怎麼解，上網找答案也還是似懂非懂，最後可是嘗試了好幾次失敗才終於刷過的呀…

先了解下題目

題目本人：Two Sum - LeetCode

我的題目解讀：

給你一串數字叫 nums
再給你一個數字叫 target
nums 這串數字裡呢，會有兩個數字加總等於 target
找出那兩個數字的 index
答案要用像 [0, 1] 這樣兩兩一組的格式寫下來傳給 LeetCode 看
LeetCode 保證答案只會有一組。

解法 ①：雙迴圈

雙迴圈解法很直覺，但 Code 跑起來速度最慢，時間複雜度是 O(n^2)，因此又常被稱為暴力解。

為什麼知道可以用雙迴圈？

我當初在網路上找答案的時候，幾乎每篇文章都是：用雙迴圈、用雙迴圈、用雙迴圈…。然後就開始寫 Code，啊不是，修但幾勒，到底你們為什麼會知道可以用雙迴圈！

嘗試把直覺口語化或視覺化

假如今天數字串 nums 是 ['5', '2', '4']，身為正常人類的第一直覺不外乎是從 5 開始往後面一個數字加加看是不是等於 target 對吧！

拿 5 出來依序加完後面的 2 跟 4 之後，會發現都不是 target，這時就換下一位 2 開始往後面加加看，然後依此類推，試著想像看看…

有沒有，就是雙迴圈呀！又因為題目保證答案只會有一組，所以只要有某兩個數字加起來是 target 就可以馬上確定他們是答案了，記得最後要 return 的是他們在 Array 裡的 index，可別在最後粗心老馬了。

那麼安心上 Code！

const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

解法 ②：Map

Map 解法的時間複雜度是 O(n)，Code 跑起來速度會比雙迴圈好很多唷！

為什麼要知道第二種解法？

一來是當面試官看出你雙迴圈用得滾瓜爛熟，或他懷疑你可能是用背的而不是真的會，很可能就會想追問變化題更加的考驗你，所以知道第二種解法不吃虧；二來就是看自己有沒有心想練更多功罷了。

大方向的思路寫在以下註解裡，就不多說了。

還是 Code

const twoSum = (nums, target) => {
  const map = {};
  for (let i = 0; i < nums.length; i++) {
    // * target - 目前迴圈跑到的數字 → 可以知道另一個數字會是幾，但不知道它是否存在於 array，存在的話也不知道 index 多少
    let anotherOne = target - nums[i];

    // * 檢查記錄了每個數字的 index 的 map 物件，如果另一個數字有被記錄在裡面，那就是它了
    // * (第 1 圈 map[anotherOne] 一定會 undefined 因為 map 物件裡還沒有東西，所以第 2 圈開始才會進到這個 if)
    if (map[anotherOne] !== undefined) {
      return [map[anotherOne], i];
    }

    // * 每跑一圈，就用 key-value 紀錄每個數字的 index (方便做檢查)
    map[nums[i]] = i;
  }
};

Ending

以上皆用傳統 for 迴圈來示範，ES6 寫法就請自行融會貫通了，還真的有遇過追加變化題是要我用 ES6 語法改寫的唷，那麼以上！

Chiyu

Blog