一种从数字列表中查找一对和的算法？

Question

假设您有以下数字列表{3,6,10,9,13,16,19},不一定按此顺序排列.现在,不知道这是集合{3,6,10}的可能组合的集合,是否存在可用于有效地找到这些组合的任何编程语言的算法.基本上,我想从总集中恢复列表 - 其中包含所有数字.什么是有效的算法,如果已经存在,我不希望重新发明轮子？

Answer 1

对于可以有任意数量元素的一般情况,这里是O(q*log(q))算法,其中q是输入列表的大小:

1. 按升序对列表q进行排序.
2. 删除最小元素m,并将其添加到结果集中.从q中删除它.
3. 迭代q.保留我们见过的数字列表.如果我们看到一个数字(我们已经看过的数字+ m),那么丢弃它.这应该保留一半的数字(所有那些不涉及m).
4. 从步骤2开始重复,直到找到所有数字.

以下是Python中此算法的实现:

def solve(q):
    q = sorted(q)
    x = []
    while q:
        x.append(q[0])

        s = [False]*len(q)
        s[0] = True
        j = 1

        for i in range(1, len(q)):
            if q[i] == q[0] + q[j]:
                s[i] = True
                j += 1
                while j < len(q) and s[j]:
                    j += 1

        q = [k for k, v in zip(q, s) if not v]
    return x

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]
from itertools import combinations
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r))
print(solve(q))

结果:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]

原始答案:

假设列表中只有3个数字,并且没有数字可以为负数:

其中两个数字必须是列表中最小的两个数字.最大的数字必须是所有三个的总和.通过减法,您可以找到第三个数字.