sum - 在列表中,python 如何查找成对的和?

64 0

我有一张单子


[1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 9]



我想找到所有对等于10,

它应该是不同的数字对:

等等


{(1, 9), (2, 8), (3, 7), (5, 5)}.



以下是我的想法,但我对下面的嵌套循环不满意:


def test(x, n):


 pair = set()


 for i in range(len(x)):


 for j in range(len(x)):


 if i!=j:


 pair.add((x[i],x[j])



时间: 原作者:

88 3

在 O(n), 中处理值的排序列表的解决方案:


values = [1, 2, 3, 3, 5, 5, 6, 7, 8, 9, 9]


target = 10



i = 0


j = len(values) - 1


solutions = set()



while j> i:


 if values[i] + values[j] <target:


 i += 1


 elif values[i] + values[j]> target:


 j -= 1


 else:


 solutions.add((values[i], values[j]))


 i += 1


 j -= 1



print(solutions)


# {(2, 8), (5, 5), (1, 9), (3, 7)}



58 1

@ThierryLathuille's 解决方案假定列表是预先排序的。 如果假设为 false,则排序列表将花费O ( n log n ) 。 相反,你可以使用 collections.Counter 实现 O(n) 时间复杂度,而对列表中每个值的可用项数量进行记帐:


from collections import Counter


counts = Counter(x)


list({frozenset((10 - n, n)): (10 - n, n) for n in counts if counts[10 - n]> (n == 10 - n)}.values())



返回:


[(1, 9), (2, 8), (3, 7), (5, 5)]



原作者:
70 3

如果我们知道我们想要的总数,我们可以休息这个问题- 对于每个数字,是列表中的( 总计- 数字)?

我们可以将列表转换为一个使用哈希查找的集合:


x = [1, 2, 3, 3, 5, 5, 5, 6, 6, 7, 8, 9, 9]



out = []


total = 10


for i in set(x):


 if (total - i) in set(x) and i <(total+1)/2:


 out.append((i, 10-i))


out



[(1, 9), (2, 8), (3, 7), (5, 5)]



原作者:
...