リスト内のX番号の合計を見つける（Python）

Question

私は整数のリストの中の合計の組み合わせを見つけようとしています。

和を含む数値の量を可変することにより制限されるので、リスト内の、例えば -

[5,2,3,9,1]、iが10の合計を見つけたいです2つの数字しかありません。

となり、プログラムは[9,1]を出力します。

私はPythonには新しく、簡単な方法はありますか？

ありがとうございました。

Answer 1

itertools.combinationsを使って強引なアプローチ：

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

これは、10にあなたにその合計をすべてのペアを与えるこれは、実行時にsuperexponentialあるので、あなたの入力が大きい場合は、より洗練されたアルゴリズムをお勧めします。

Answer 2

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] 

Combinations反復可能なオブジェクト（することができますオブジェクトのループ以上）から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)] 

Answer 3

ls = [5, 2, 3, 9, 1] 
sum = 10 

while ls: 
    num = ls.pop() 
    diff = sum - num 
    if diff in ls: 
     print([num, diff]) 

Answer 4

、ここ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を使用する必要がありました。それほど複雑ではありません。

itertools.combinationsバージョン@roippiよりも読むのが難しいと思いますが、整数のリストが大きい場合は非常に高速です。私は通常、それを実行するマシン時間にコードを読む人間の時間を評価しますが、どのような考慮が勝つかは、あなたの正確な状況に依存します。

バージョンitertoolsとは異なり、両方の要素が重複しない限り、重複ペアは返されません。 EGでは、[4、3、6、6]のリストを検討する。 itertoolsバージョンは、2つの異なる（4,6）ペアを生成し、両方を返します。このバージョンでは、最初の6と一致するとすぐに消費された4が考慮され、1つだけが返されます。重複が必要な場合は、Counterの代わりにsetが機能しますが、5の特殊なケースは、@ lollercoasterの答えに示されているように繰り返しセットを構築しない限り、より複雑になります。

Answer 5

はすべてこれまでのO（N^2）またはより悪いので、ここではO（N）ソリューションですされている：OPが尋ねたので

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））を得ることができるはずです。

Answer 6

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 

Answer 7

#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)