[LeetCode] 001. Two Sum

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].


解題邏輯與實作

這一題算是LeetCode中的Hello World吧,網路上還流傳著平生不識TwoSum,刷盡LeetCode也枉然這句話呢,可見這題是多麼的廣為人知(?)

簡單來說這題是要從給定陣列中找出兩個數字,其總和為給定的target,最後還這兩個數字的索引值。每題必定只有一個解,且每個數字並不會被重述使用。


暴力法

最直覺想到的當然是暴力法,但果不其然Time Limit Exceeded,畢竟用暴力法的時間複雜度是O(n2)O(n^2)

class Solution:        
    def cal_sum(self, num_1 , num_2):
        return num_1 + num_2
            
    def twoSum(self, nums, target):        
        size = len(nums)
        for idx1 in range (size) :
            num_1 = nums[idx1]

            for idx2 in range(idx1+1 ,size):
                num_2 = nums[idx2]

                s = self.cal_sum(num_1,num_2)
                if s == target:
                    return [idx1,idx2]
                
        raise RuntimeError("No two sum solution") 


雜湊表(Hash table)

既然暴力法時間複雜度暴表,那就拿空間換取時間吧!另外設立一個HashMap儲存走訪過得結果,當一個數字進來後去檢查,差值是否存在HashMap中,若存在則回傳結果,實做步驟如下:

  1. 讀入陣列中一值 n,並計算其差值 diff = target - i
  2. 檢查差值diff ,是否存在於HashMap中,
    1. 不存在,將 n 與所對應的索引值作為 key–value pair,存入HashMap中。
      • 因為,題目要求最後回傳的結果是兩個數字的索引值,所以必須一併紀錄索引值。
    2. 存在,則取出差值diff所對應的索引值,與當前索引值合併成一個陣列回傳。



程式碼

class Solution:        
            
    def twoSum(self, nums, target):
        keys = {}
        for i in range(len(nums)):
            value =  nums[i] 
            if target - value in keys:
                return [keys[target - value], i]
            if value not in keys:
                keys[value] = i
                
        raise RuntimeError("No two sum solution") 



[LeetCode] 解題目錄 -> 這裡走

留言

這個網誌中的熱門文章

Genymotion 模擬器安裝篇:In ubuntu14.04 LET