DOJO004

Dashool 創辦人
喜歡調酒
Rails、Nextjs、TypeScript

來刷 LeetCode 吧! 07 001. Two Sum

LeetCode

https://leetcode.com/problems/two-sum/

題目分析

給一個 array “nums”、整數 “target”。

回傳一個 array，裡面包含兩個整數，這兩個整數代表的是在 “nums” 當中的 index，兩數相加 = “target”。

第一直覺

透過兩個 for 迴圈，暴力破解。

時間複雜度 O(n^2)

var twoSum = function (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];
      }
    }
  }
};

HashTable

上方使用雙迴圈的效率不佳，我們可以宣告一個新的記憶體位置，去紀錄運算的結果。
透過反向思考，從原本的 nums 兩數相加 = target，變成由 target - nums [ i ] 找到所屬的 index。

var twoSum = function (nums, target) {
  let hashTable = {};
  for (let i = 0; i < nums.length; i++) {
    if (target - nums[i] in hashTable) {
      return [i, hashTable[target - nums[i]]];
    }
    hashTable[nums[i]] = i; // 將 nums[i] 的 index 存入 hashTable。 ex: hashTable = { 2:0 }
  }
};