从整数列表中找到所有数字对的最有效方法是什么，这些整数加起来等于一个单独的给定整数？

Question

我昨天接受了采访，被要求提供一种方法来从列表中找到所有数字对，这些数字加起来等于一个整数，该整数与列表分开给出。该列表可以无限长，但是例如：

numbers = [11,1,5,27,7,18,2,4,8]
sum = 9

pairs = [(1,8),(5,4),(7,2)]

我对列表进行排序并消除所有大于 sum 数字的数字，然后执行两个嵌套的 for 循环以获取每个索引并遍历其他数字以检查它们是否总和给定的数字，但被告知有更有效的方法...

我一直在努力弄明白，但一无所获，除了向后进行嵌套迭代，但这似乎只是稍微更有效率。

有什么想法吗？

Answer 1

它有点经典，但不确定 Whosebug 是否适合提出此类问题。

列表排序为升序
两个迭代器，一个从列表末尾开始降序i1，一个从列表开头开始升序i2
循环

while i1 > i2
    if (list[i1] + list[i2] == target)
        store {list[i1], list[i2]) in results pairs
        i1--
        i2++
    else if (list[i1] + list[i2] > target)
        i1--
    else if (list[i1] + list[i2] < target)
        i2++

如果您避免排序算法，这应该在 O(n) 中，列表的长度为 n，这可以在 O(n log n)[=14 中平均通过快速排序完成=]

注意：该算法没有考虑输入列表有多次相同数字的情况

Answer 2

这可以在O(n)时间和O(n)辅助下完成space；测试集合的成员资格需要 O(1) 时间。由于输出也占用O(n)space，辅助space应该不是什么大问题。

def pairs_sum(numbers, k):
    numbers_set = set(numbers)
    return [(x, y) for x in numbers if (y := k - x) in numbers_set and x < y]

示例：

>>> pairs_sum([11, 1, 5, 27, 7, 18, 2, 4, 8], 9)
[(1, 8), (2, 7), (4, 5)]

从整数列表中找到所有数字对的最有效方法是什么，这些整数加起来等于一个单独的给定整数？

What is the most efficient way to find all pairs of numbers from a list of integers which add up to a separate given integer?

math

subset