LeetCode 刷題紀錄｜1. Two Sum (Easy)

Roy Wang

Published in

RoyWannago

3 min readNov 12, 2020

第一題是經典 Two Sum

Two Sum

Question:

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.

Answers

Brute Force
Hash Table — Two-Pass
Hash Table — One-Pass

1. Brute Force 最暴力解

Go through two loops to compare one and another to see if the two numbers meet the target

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

Time complexity: O(n²)
Space complexity: 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 Two-Pass

Try to lower the time complexity with space complexity
We want to check if the element exists
We want to track the index of the element
Lookup in the hash table takes linear time if there is no collision

以空間換取時間，因為Hash Table的look up只需O(1)，很適合用在這題。從原本的兩層 loop: O(n * n) 進步成兩個 loop: O(n+n) = O(n)。

Hash Table 的架構會長這樣 value: ‘index’：

Input: [7, 2, 11, 20]
Hash Table: {7: ‘0’, 2: ’1', 11: ‘2’, 20: ‘3’}

Time complexity: O(n)
Space complexity: O(n)

var twoSum = function(nums, target) {
  let map = {};  // First loop: add value & index into hash table  for (let i = 0; i < nums.length; i++) {
    map[nums[i]] = i;
  }  // Second loop: 
  // check if their complement(= target-value) in the hash table and  
  // complement cannot be itself so we check with the index  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];    // if found and it is not itself, return
    if (map[complement] != null && map[complement] != i) {
      return [i, map[complement]];
    }
  }
}

3. Hash Table — One-Pass

We check if the complement exists in the first loop when creating the bucket
We can use in to check if the specified property is in the specified object or its prototype chain (Reference)

在 loop 時就直接先找目前為止建立起來的 hash table 裡面有沒有該數的complement，可以加速查找的速度，一次 loop 就可以結束了。回傳該數的index 跟存在裡面的 index。注意建立 hash table 的動作是放在 if statement 之外的，不論有沒有找到都要建立起 hash table。

Javascript:

var twoSum = function (nums, target) {
  let map = {};  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];    // Chech if complement already in the table
    if (complement in map) {
      // if found, return
      return [map[complement], i];
    }
    
    // add value & index into hash table
    map[nums[i]] = i;
   }  return null;
};

Python:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = {}
        
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashtable:
                return [hashtable[complement], i]
            hashtable[nums[i]] = i
        return

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

歡迎留言討論或是到我的Socials找我~新手上路，如果有寫錯的地方歡迎大力糾正，謝謝觀看！

About Roy

Social Media
Facebook — RoyWannago
Twitter — @roywannago
Instagram — @royflwdesign
Website — roywannago.com

LeetCode 刷題紀錄 ｜1. Two Sum (Easy)