Leetcode - Two Sum

2020-04-14 meeting PV:

在面試時，如果順利解完白板題了，面試官可能會接著問:

“這樣的時間複雜度是多少?”

“還能更快嗎?”

所以，我們試著從簡單的問題來學習如何分析時間複雜度xD

Time complexity

試圖用個不嚴謹的方法來理解他，想像有一個計數變數count = 0在你的程式裡

每執行一次你的程式count就會+1，請問執行完後count會等於多少?

這!就是時間複雜度

接下來考慮幾個Case:

variable assign: $O(1)$
1
2
x = 0
count += 1
loop: O(N)
1
2
for _ in range(N):
count += 1

nested loop(2 level): $O(N^2)$

1
2
3

for _ in range(N):
  for _ in range(N):
    count += 1

nested loop(2 level) + loop: $O(N) + O(N^2) \rightarrow O(N^2)$

upper bound

for _ in range(N):
  for _ in range(N):
    count += 1
for _ in range(N):
  count += 1

常見的還有sort通常時間複雜度為O(NlogN)、tree-based recursive的時間複雜度為O(2^N)…不過大概有個概念就好

接下來進到本週Leetcode，來探討不同解法的時間複雜度，以及他們對於效能上的差異

LeetCode 1. Two Sum

Soultion 1. double loop

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.

這題要返回index，所以不應該對list做任何變動

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return (i, j)

時間複雜度: $O(N^2)$

1 2	Runtime: 6196 ms, faster than 5.34% of Python3 online submissions for Two Sum. Memory Usage: 14.9 MB, less than 12.55% of Python3 online submissions for Two Sum.

Solution 2. Dict(hash table)

先把所有的值跟index都記錄下來，然後掃一次list，如果紀錄中存在target - nums[i]，則這就是一組解

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

時間複雜度: $O(N)$

1 2	Runtime: 44 ms, faster than 91.83% of Python3 online submissions for Two Sum. Memory Usage: 15.1 MB, less than 5.34% of Python3 online submissions for Two Sum.

python的dictionary: hash table?

這裡用到了一個資料結構: dictionary，或者，在其他語言裡面稱作hash table
查詢最快可以是$O(1)$

怎麼做到的?

空間換時間
透過一個hash function把data轉換成index，然後存到array[index]上

如果array[index]上已經有資料?

在該位置上串linked list
- 之後在linked list上搜尋就需要遍歷一次list
好的hash function很重要，考慮以下hash function: F(data)=0，也就是任意的資料都給予0的index，此時hash table查找的時間複雜度就會變O(N)
- 因為等同於在一個linked list上查找

結論:

python dict()背後用到的資料結構是hash table，查找時間複雜度通常是$O(1)$

類似題型

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

這題不是要回傳index，而是要回傳可以湊到0的數字集合

18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

這題不是要回傳index，而是要回傳可以湊到target的數字集合

總結

針對不同情境、應用使用不同的資料結構、演算法能夠大大提升效能

簡單的針對程式來分析時間複雜度是個還不錯的好習慣

不過Python提供太多lib了，有時候有些東西不好分析，就大概有個概念就好