LeetCode (1) Two Sum (python)

紀錄一下刷題, 第一題Two Sum (difficulty: Easy)

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

給一個list (list內是數個int)
再給一個target (一樣是int)
找出list內的哪兩個數加起來是target, 回傳兩個數的index
簡單來想,使用兩個for loop每個數組都加一次就解決了

for i in range(len(nums)):
    left = nums[i+1:]
    for j in range(len(left)):
        if (nums[i] + left[j]) == target:
            return i, j+i+1

在submit後,

兩個for迴圈太花時間了…

#看到的另一種寫法
k = 0
for i in nums:
    k += 1
    if target - i in nums[k:]:
        return(k - 1, nums[k:].index(target - i) + k)

看了下解答,官方給出了另外兩個答案

Two-pass Hash Table

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

We reduce the look up time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say “near” because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.

A simple implementation uses two iterations. In the first iteration, we add each element’s value and its index to the table. Then, in the second iteration we check if each element’s complement (target−nums[i]) exists in the table. Beware that the complement must not be nums[i]itself!

hash_table={}
for i in range(len(nums)):    # 先做一個hash table
    hash_table[nums[i]]=i
for i in range(len(nums)):
    if target-nums[i] in hash_table:
        if hash_table[target-nums[i]] != i:
            return [i, hash_table[target-nums[i]]]
return []

One-pass Hash Table

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

hash_table = {}
for i, num in enumerate(nums):
    if target - num in hash_table:
        return([hash_table[target - num], i])
        break    # 看到有人在這加了break, 理論上不會執行到, 但時間卻會比較短
    hash_table[num] = i
return([])

小結論

TwoSum這個題目有三種解法

1. 兩個for 迴圈從頭加到尾
2. 創一個Hash Table, 再使用for 迴圈去尋找答案
3. 邊創Hash Table, 邊看是否達到解答, 達到就返回