наиболее эффективный способ найти сумму двух чисел

Question

Я изучаю проблему: при произвольном списке, в данном случае это [9,15,1,4,2,3,6], найти любые два числа которая суммируется с заданным результатом (в этом случае 10). Какой был бы самый эффективный способ сделать это? Мое решение - n с точки зрения большой записи 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 

Answer 1

Я думаю, это решение будет работать ....

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 

Answer 2

O (п журнал п) решение

Сортировка списка. Для каждого номера x, binary search за S - x в списке.

О (п) решение

Для каждого номера x, если у вас есть S - x в хэш-таблице. Добавить x в hash table.

Обратите внимание, что если ваши номера действительно маленькие, хеш-таблица может быть простым массивом, где h[i] = true if i exists in the hash table and false otherwise.

Answer 3

Используйте словарь для этого и для каждого элемента в списке найдите total_required - item в словаре. Я использовал collections.Counter здесь, потому что set может выйти из строя, если total_required - item равен текущему элементу из списка. В целом сложность 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)