Two Sum


Posted by rockyooooooo on 2022-03-26

1. Two Sum

第一天的 leetcode 系列,先小試身手,從最簡單經典的 Two Sum 開始做做看。
之前就有解過這題,那次解完之後實在不知道還可以怎麼解比較好,於是就偷看了別人的答案。
沒想到還記得,所以稍微想了一下,測試完沒問題就直接 Submit 了。

最基礎解法:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
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]
    }
  }
};

沒什麼特別的,就是把 nums 直接雙層 for loop 過去。
但這個解法的時間複雜度是 $O(N^2)$

$O(N)$解法

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const hashTable = {}
  for (let i = 0; i < nums.length; i++) {
    if (hashTable.hasOwnProperty(nums[i])) return [i, hashTable[nums[i]]]
    hashTable[target - nums[i]] = i
  }
};

策略是,把 for loop 過的 element 所需要的對應數字記下來,當 loop 到那個數字的時候,就表示找到答案了。
例如:

Input: nums = [2, 5, 7, 11], target = 9

i = 0

nums[0] = 2
target - 2 = 7
把 7 跟這個 index 記錄起來

hashTable = {
  7: 0
}

i = 1

nums[1] = 5
找 hashTable 裡面有沒有 5 這個 key,沒找到,表示前面找過的數字沒有一個加 5 會等於 target 的。
target - 5 = 4
繼續加入 hashTable,此時 hashTable 長這樣:

hashTable = {
  7: 0,
  4: 1
}

i = 2

nums[2] = 7
找 hashTable 裡面有沒有 7 這個 key,有找到,表示前面第 0 個 element 可以跟他配對,所以答案是 [0, 2]


#Leetcode #twosum







Related Posts

菜比八寫後端(2) - MySQL語法

菜比八寫後端(2) - MySQL語法

JavaScript內建函式

JavaScript內建函式

基礎電腦科學:演算法概要

基礎電腦科學:演算法概要


Comments