最有效的方法來找到兩個數字的總和

我正在調查一個問題：給出一個任意列表，在這種情況下，它是[9,15,1,4,2,3,6]，找到任何兩個數字這將總結給定的結果（在這種情況下爲10）。什麼是最有效的方式來做到這一點？我的解決方案是用大O符號表示，即使我已經過濾和排序數字，我確信有一種更有效的方法。在此先感謝最有效的方法來找到兩個數字的總和

myList = [9,15,1,4,2,3,6] 
myList.sort() 
result = 10 
myList = filter(lambda x:x < result,myList) 
total = 0 
for i in myList: 
    total = total + 1 
    for j in myList[total:]: 
     if i + j == result: 
      print i,j 
      break

來源

2015-02-07 godzilla

提示：不要使用標準的Python關鍵字，如'list'變量的名字，因爲它覆蓋內置的關鍵字。叫它「mylist」，或者更合適的東西，比如'numbers'。 – Evert 2015-02-07 12:29:34

我認爲，這個解決方案會工作....

list = [9,15,1,4,2,3,6] 
result = 10 
list.sort() 
list = filter(lambda x:x < result,list) 
myMap = {} 

for i in list: 
    if i in myMap: 
     print myMap[i], i 
     break 
    myMap[result - i] = i

來源

2015-02-07 13:11:52 godzilla

爲O（n log n）的解決方案

排序列表。對於列表中的每個號碼x,binary search爲S - x。

爲O（n）解決方案

對於每個編號x，看看你是否在哈希表中有S - x。將x添加到hash table。

請注意，如果您的數字非常小，則散列表可以是一個簡單的數組，其中h[i] = true if i exists in the hash table and false otherwise。

來源

2015-02-07 12:33:23 IVlad

請注意，O（n）解決方案是Ashwini Chaudhary的答案更詳細地顯示的。 – 2015-02-07 16:31:22

使用字典爲此和列表中的每個項目在字典中查找total_required - item。我在這裏使用了collections.Counter，因爲如果total_required - item等於列表中的當前項目，set可能會失敗。總體複雜性是O(N)：

>>> from collections import Counter 
>>> def find_nums(total, seq): 
    c = Counter(seq) 
    for x in seq: 
     rem = total - x 
     if rem in c: 
      if rem == x and c[rem] > 1: 
       return x, rem 
      elif rem != x: 
       return x, rem 
...   
>>> find_nums(2, [1, 1]) 
(1, 1) 
>>> find_nums(2, [1]) 
>>> find_nums(24, [9,15,1,4,2,3,6]) 
(9, 15) 
>>> find_nums(9, [9,15,1,4,2,3,6]) 
(3, 6)

來源

2015-02-07 12:38:41

爲什麼要檢查c [rem]> 1？這並不明顯。你能解釋一下嗎？ – kmario23 2015-02-08 21:29:23

@ mario23如果沒有這個條件'find_nums（2，[1]）'會返回'（1，1）'，我們需要區分當前的數字'x'和'rem'。 – 2015-02-08 22:03:14

最有效的方法來找到兩個數字的總和

回答

相關問題