iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 2
0
自我挑戰組

Leetcode新手挑戰30天系列 第 2

#1 Two Sum - 研究其他種解法

  • 分享至 

  • xImage
  •  

寫在開頭

昨天解Two Sum的時候用巢狀迴圈的方式寫,最後Submit的結果是
https://ithelp.ithome.com.tw/upload/images/20190903/20113393dizTSmETyP.png
但在昨天找到的文章分享中,看到幾個解法,今天想在研究研究

其他解法1:

k = 0
for i in nums:
    k += 1
    if target - i in nums[k:]:
        return(k - 1, nums[k:].index(target - i) + k)

這個做法只剩下一個迴圈,降低了時間複雜度,
nums[k:]這個寫法沒學過,覺得很特別,就查了"Python冒號"的用法
冒號是一個像從索引a到索引b的概念
另外一種倒數索引的方法是用寫負號表示倒數第幾個索引
像nums[-1]就是指倒數第一個
最後有一種寫法 x[:,::-1]
兩個冒號分別代表開始和結束,而-1則代表倒著顯示陣列元素

其他解法2:

hash_table={}
for i in range(len(nums)):
    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 []

這個是先使用了一層的迴圈,把原本的陣列變成Hash table,
然後再用另一層迴圈去判斷題目要的答案
不過文章中提到解法1的runtime是1048ms;解法2的runtime是40ms;
不太曉得為什麼改用hash table就會快這麼多,明天繼續研究.

後來查資料時發現這篇文章講Hash Table寫得很詳細,最後決定暫時不另寫一篇了
白話的 Hash Table 簡介

參考資料:

LeetCode (1) Two Sum (python)
Python初學重點 (07) – List
Python中陣列,列表:冒號的靈活用法介紹(np陣列,列表倒序)
白話的 Hash Table 簡介


上一篇
#1 Two Sum
下一篇
#9 Palindrome Number
系列文
Leetcode新手挑戰30天31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言