iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 0
0
Software Development

從零到一:五個月轉職工程師大挑戰系列 第 1

刷題紀錄 1: Two Sum

分享刷題的紀錄
用的語言是 Javascript


第一題是經典 Two Sum

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 105
  • 109 <= nums[i] <= 109
  • 109 <= target <= 109
  • Only one valid answer exists.

Answer


1. 最暴力解

就是一個個抓起來比看配不配

  • Time: O(n^2)
  • Space: O(1)
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i+1; j < nums.length; j++) {
            if (nums[i]+nums[j] === target) {
                let result = [i, j]
                return result
            }
        }
    }
};

2. Hash Table

  1. 降低 time complexity
  2. 我們想要確認element是否存在
  3. 我們想知道 element 的 index 位置
  4. 如果沒有 collision, hash table 的 lookup 是 linear time
  • Time: O(n)
  • Space: O(n)
var twoSum = function(nums, target) {
  let map = {}
  // 第一個 loop: 
  // 把 value & index 加進去 hash table
  for (let i = 0; i < nums.length; i++) {
    map[nums[i]] = i
  }
  // 第二個 loop: 
  // 檢查他們的complemet(= target-value)是否在table中, 
  // 且不能為他自己, 用 index 來檢查
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]
    // 若有找到且不為自己,回傳
    if (map[complement] != null && map[complement] != i) {
      return [i, map[complement]]
    }
  }
}

還有另外一個解是存被尋找的數
在第一個 loop 存進去 bucket 的同時,我們也找看看有沒有 complement 已經在裡面了

  • Time: O(n)
  • Space: O(n)

系列文
從零到一:五個月轉職工程師大挑戰1

尚未有邦友留言

立即登入留言