我正在尝试在整数列表中查找一组数字，其和等于给定值。
这个数字的数量由一个变量限制，例如在列表[5,2,3,9,1]中，我想找到两个数字的和为10。
因此程序将打印出[9,1]。
我是Python的新手，是否有更容易的方法？
谢谢。
在列表中找出X个数的总和（Python）
7
- Krypton
2
你想找到列表中哪两个数字相加等于10？ - jramirez
请查看itertools模块。 - rlms
8个回答
10
from itertools import combinations
l = [5,2,3,9,1]
for var in combinations(l, 2):
if var[0] + var[1] == 10:
print var[0], var[1]
组合可以从可迭代对象中创建所有可能的元组组合（一个您可以循环遍历的对象）。让我来演示一下：
>>> [var for var in combinations([1,2,3,4,5], 2)]
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
>>> [var for var in combinations([1,2,3,4,5], 3)]
[(1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5), (2, 3, 4), (2, 3, 5), (2, 4, 5), (3, 4, 5)]
- Games Brainiac
1
这是获取时间复杂度的最佳方法吗？ - lalithkumar
4
到目前为止，所有的解决方案都是O(N^2)或更糟，因此这里有一个O(N)的解决方案：
l = [7, 9, 6, 4, 2]
s = set([l[0]])
sum = 10
for num in l[1:]:
diff = sum - num
if diff in s:
print num, diff
else:
s.add(num)
因为楼主提出了问题，所以这里给出一个更加通用的解决方案。我们有：
numbers（数字列表）sum（期望的和）n（我们希望将其求和为sum的元素数）
最简单的方法是：
def find_sum_tuple(numbers, sum, n):
return [tup for tup in itertools.combinations(numbers, n) if sum(tup) == sum]
然而，从渐近性能来看并不是最佳的。正如我上面所示，通过更聪明地缓存n-1大小的和，你应该能够获得渐近O(|numbers|^(n-1))。
- lollercoaster
4
我不同意我的
Counter解决方案是O(N^2)的。一次遍历创建Counter，一次遍历搜索对和N个字典查找。这个版本接近于我的，但无法正确处理像 [4, 6, 6] 这样的情况。我认为这个想法有一些好处 - 只需使用Counter而不是set，您可能会从仅迭代一次中获得性能优势。根据 Counter 构造函数处理列表的速度比进行多次编辑快多少 - C实现可能会打败算法改进。 - Peter DeGlopper的确如此，但是考虑到问题要求的是“一种组合”，而不是“所有组合”，因此这个答案在2N范围内就能解决问题，而不是你的3N。这两者之间并没有太大的区别 - 所以我们都是线性的！ - lollercoaster
是的，通常只有O(N)而不是O(N^2)才是重要的。而且事实证明，在可能出现重复项的情况下，行为可能很重要 - 在这个小例子中，
itertools会找到两次(4,6)。原帖没有指定，因此您的版本可能更接近意图。 - Peter DeGlopper虽然我更喜欢不使用itertools的方法，但我最初的意图是有一个变量来确定需要多少个数字才能得到总和。
因此，该变量可以是3或2，并且仍然可以得到结果...
话虽如此，是否有一种优雅的方法可以在不使用itertools的情况下完成它？（请原谅我，因为我说过我对Python还很陌生 :)） - Krypton
3
使用 itertools.combinations 的暴力方法：
In [6]: [pair for pair in itertools.combinations(li,2) if sum(pair) == 10]
Out[6]: [(9, 1)]
这将为您提供所有总和为10的数字对。这种算法的运行时间超级指数级，因此如果您的输入很大，则需要更复杂的算法。
- roippi
2
我认为你可以从理论上利用这个事实来节省一些处理时间，即一旦你知道了第一个数字，你也知道了第二个数字，并且可以检查它是否存在于列表中（可能使用从列表创建的
collections.Counter对象来加速重复成员资格测试，每输出一对就递减），但这会比这更令人困惑。在绝大多数情况下，清晰度可能胜出。 - Peter DeGlopper@PeterDeGlopper，是的，我添加了有关时间复杂度的注释。我想对于大多数用途来说，这已经足够了。 - roippi
3
ls = [5, 2, 3, 9, 1]
sum = 10
while ls:
num = ls.pop()
diff = sum - num
if diff in ls:
print([num, diff])
- Darrick Herwehe
2
如果仅仅为了代码压缩的目的，这里提供一种使用collections.Counter的方法：
import collections
integers_list = [5,2,3,9,1]
integer_counts = collections.Counter(integers_list)
for x in integers_list:
y = 10 - x
if (x != y and integer_counts[y]) or (x == y and integer_counts[y] > 1):
print (x, y) # Or, if building a new list, append instead of print
integer_counts.subtract((x, y))
collections.Counter是在2.7版本中添加的。如果您使用的是早期版本，则需要使用defaultdict代替。它并不复杂。
我认为这比@roippi发布的itertools.combinations版本更难阅读，但如果整数列表很大，则应该会更快。我通常重视人类阅读代码的时间，而不是机器执行代码的时间，但哪种考虑因您的具体情况而异。
与itertools版本不同，除非两个元素都重复，否则它将不返回重复对。例如，考虑一个列表[4,3,6,6]。 itertools版本将生成两个不同的(4,6)对并将它们都返回；此版本将在匹配到第一个6时考虑4已被消耗，并仅返回一个。如果需要重复项，则可以使用set代替Counter - 虽然5的特殊情况会变得更加复杂，除非您按@lollercoaster答案中所示进行迭代构建集合。
- Peter DeGlopper
0
a = [5,2,3,9,1]
b = []
for i in range(len(a)):
for j in range(i + 1, len(a)):
if (a[i] + a[j] == 10):
b.append((a[i],a[j]))
print(b)
- Bhaskar Pathak
1
2请记住，Stack Overflow 不仅旨在解决当前的问题，还要帮助未来的读者找到类似问题的解决方案，这需要理解底层代码。对于我们社区中的初学者和不熟悉语法的成员来说，这尤其重要。鉴于此，您能否编辑您的答案，包括您正在做什么以及为什么您认为这是最好的方法的解释？ - Jeremy Caney
0
lst = [5,2,3,9,1]
lstLen = len(lst)
pair = 0
for i in range(lstLen):
for j in range(lstLen):
if(j <= i ): continue
if((lst[i] + lst[j]) == 10):
pair +=1
print "[%s, %s]" % (lst[i], lst[j])
print "number of pair = %s" % pair
- Giao Nguyen
0
#for unsorted array - complexity O(n)
def twoSum(arr, target):
hash = {}
if len(arr) < 2:
return None
for i in range(len(arr)):
if arr[i] in hash:
return [hash[arr[i]], i]
else:
hash[target - arr[i]] = i
return None
twoSum([3,2,8,6],11)
- Zorro
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接