分享刷題的紀錄
用的語言是 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)