如何在列表中检查三个整数的总和是否与另一个整数匹配？（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循环结构，如下所示：

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

但是，由于我的整数列表包含超过10万个项目，这将使用太多的内存并且需要太长时间。

有没有办法在不使用过多内存或花费过长时间的情况下找到A、B和C的解决方案？提前致谢。

- Jon Warren

---

使用 itertools.combinations。 - inspectorG4dget

注意：如果你的列表是[1,2,3]，目标是9，那么你当前的循环会找到一个答案，即3+3+3等于9，尽管3只在你的列表中出现一次。因此，建议考虑使用itertools.combinations，正如@inspectorG4dget所推荐的那样。 - RobertB

@RobertB 这是可以接受的，虽然我的列表中只出现一次，但我仍然被允许重复项。 - Jon Warren

@RobertB 对不起，我以为我在第二段括号里解释得足够清楚了，我会尝试编辑那部分内容，使其更易理解！ - Jon Warren

为什么不尝试一种非比较排序，比如基数排序？虽然会有一些内存开销，但至少对于每种情况它的运行时间复杂度都是O(N)，然后你可以使用更优化的算法来查找A、B和C。 - Patrick Roberts

Answer 1

你可以使用类似 set 这样的东西，将运行时间从 n^3 减少到 n^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

如果你想节省内存，你也可以对列表进行排序并使用二分查找。

- m7mdbadawy

---

我不确定这是O(n^2)。在双重循环内测试集合包含的“in”语句不是常数时间。也许它是O((n^2) logn)。 - RobertB

集合使用哈希表实现，可以在O(1)的时间内进行查找。这里的操作符利用了哈希表。 - m7mdbadawy

@RobertB 我认为set中的in操作是O(1)，因为值的访问是由于哈希值而平摊的。这就是为什么这个答案非常聪明的原因。 - Delgan

根据 https://wiki.python.org/moin/TimeComplexity ，它的最佳情况是 O(1)，最坏情况是 O(n)，对于这样一个大集合，我认为可能 O(log n) 是更好的近似值。但无论如何，它都比 O(n^3) 好... - RobertB

做了一个实际测试。即使n=100,000，in语句也非常快，所以我错了。 - RobertB

@RobertB：你并没有严格错误，只是最佳情况的行为非常普遍。你需要一个精心制作的非相等值集合，使它们具有相同的哈希值才能获得O(N)的性能。 - Blckknght

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

- inspectorG4dget

Answer 3

借鉴@inspectorG4dget的代码，这里有两个修改：

1. 如果C < B，那么我们可以短路循环。
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。

- Brent Washburne