7

我正在尝试在整数列表中找到总和的组合。

包含总和的数字数量受变量限制，例如在列表中 -

[5,2,3,9,1]，我想找到 10 的总和，只有 2 个数字。

这样程序就会打印出 [9,1]。

我是python新手，有没有简单的方法？

谢谢你。

4

7 回答 7

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]

组合tuples从可迭代对象（您可以循环的对象）创建所有可能的组合。让我演示一下：

>>> [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)]
于 2013-10-25T21:02:14.307 回答
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)

由于OP提出了要求，因此对解决方案进行了更一般的了解。我们有：

  • numbers（数字列表）
  • sum（所需金额）
  • n（我们希望求和的元素数量sum）

最简单的方法如下：

def find_sum_tuple(numbers, sum, n):
  return [tup for tup in itertools.combinations(numbers, n) if sum(tup) == sum]

但是，就渐近性能而言，并不是最好的。正如我在上面展示的那样，您应该能够通过更聪明和缓存大小总和来获得渐近 O(| numbers|^( -1)) 。nn - 1

于 2013-10-25T21:35:49.507 回答
3 
ls = [5, 2, 3, 9, 1]
sum = 10

while ls:
    num = ls.pop()
    diff = sum - num
    if diff in ls:
        print([num, diff])
于 2013-10-25T21:06:18.107 回答
3

蛮力方法使用itertools.combinations：

In [6]: [pair for pair in itertools.combinations(li,2) if sum(pair) == 10]
Out[6]: [(9, 1)]

这为您提供了总和为 10 的所有对。这在运行时是超指数的，因此如果您的输入很大，您将需要更复杂的算法。

于 2013-10-25T20:58:14.910 回答
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 中添加。对于早期版本，您需要使用 adefaultdict代替。它并不复杂。

我认为这比itertools.combinations@roippi 发布的版本更难阅读，但如果整数列表很大，它应该会更快。我通常重视人工阅读代码的时间而不是机器执行代码的时间，但哪种考虑获胜将取决于您的具体情况。

与itertools版本不同，这不会返回重复的对，除非两个元素都重复。例如，考虑 [4, 3, 6, 6] 的列表。该itertools版本将生成两个不同的 (4, 6) 对并将它们都返回；此版本在与前 6 个匹配后立即考虑 4 个消耗，并且将仅返回一个。如果需要重复， aset而不是 aCounter会起作用-尽管 5 的特殊情况会变得更加复杂，除非您像@lollercoaster 的答案中所示那样迭代地构建集合。

于 2013-10-25T21:07:26.210 回答
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
于 2014-09-03T22:17:44.097 回答
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)
于 2017-05-28T01:07:54.787 回答