Как проверить, соответствует ли сумма из 3 целых чисел в списке другому целому? (python)

Question

Вот моя проблема:

У меня есть большое целое число (от 0 до 2^32-1). Назовем это число X. У меня также есть список целых чисел, в настоящее время несортированный. Все они являются уникальными числами, больше 0 и меньше X. Предположим, что в этом списке имеется большое количество предметов, скажем, более 100 000 предметов.

Мне нужно найти до 3-х цифр в этом списке (назовем их A, B и C), которые составляют до X. A, B и C все должны быть внутри списка, и они могут быть повторяется (например, если X равно 4, я могу иметь A = 1, B = 1 и C = 2, хотя 1 будет отображаться только один раз в списке).

Может быть несколько решений для A, B и C, но мне просто нужно найти одно возможное решение для каждого из самых быстрых способов.

Я попытался создать для структуры петли, как это:

For A in itemlist: 
    For B in itemlist: 
    For C in itemlist: 
     if A + B + C == X: 
     exit("Done") 

Но поскольку мой список целых чисел содержит более 100 000 пунктов, это использует слишком много памяти, и было бы слишком долго.

Есть ли способ найти решение для A, B и C без использования безумного объема памяти или принятия безумного времени? Заранее спасибо.

Answer 1

вы можете уменьшить время работы от п^3 п^2, используя набор что-то вроде этого

s = set(itemlist) 
for A in itemlist: 
    for B in itemlist: 
     if X-(A+B) in s: 
      print A,B,X-(A+B) 
      break 

Вы также можете отсортировать список и использовать бинарный поиск, если вы хотите, чтобы сохранить память

Answer 2

import itertools 

nums = collections.Counter(itemlist) 
target = t # the target sum 
for i in range(len(itemlist)): 
    if itemlist[i] > target: continue 
    for j in range(i+1, len(itemlist)): 
     if itemlist[i]+itemlist[j] > target: continue 
     if target - (itemlist[i]+itemlist[j]) in nums - collections.Counter([itemlist[i], itemlist[j]]): 
      print("Found", itemlist[i], itemlist[j], target - (itemlist[i]+itemlist[j])) 

Answer 3

Заимствуя @ inspectorG4dget КОДЕКС, это имеет две модификации:

1. Если C < B то мы можем шор t-контур петли.
2. Использовать bisect_left() вместо collections.Counter().

Это, кажется, работает быстрее.

from random import randint 
from bisect import bisect_left 

X = randint(0, 2**32 - 1) 
itemset = set(randint(0,X) for _ in range(100000)) 
itemlist = sorted(list(itemset)) # sort the list for binary search 
l = len(itemlist) 

for i,A in enumerate(itemlist): 
    for j in range(i+1, l):   # use numbers above A 
     B = itemlist[j] 
     C = X - A - B    # calculate C 
     if C <= B: continue  
     # see https://docs.python.org/2/library/bisect.html#searching-sorted-lists 
     i = bisect_left(itemlist, C) 
     if i != l and itemlist[i] == C: 
      print("Found", A, B, C) 

Чтобы уменьшить число сравнений, мы проводим A < B < C.