如何迭代列表中的每个元素并将其与另一个元素相加以找到一个数字？

Question

我正在接受编程挑战并且遇到了这个问题，我不知何故被困住了。我得到了一个清单： [10, 13, 15, 18, 20, 15] 而且我必须找出其中任何元素的总和是否会提供结果 30 并且输出应该是计数如我们所见，我们有两种可能性，10+20 = 30 和 15+15，因此计数为 2。但是怎么做呢，应该使用for循环还是itertools或者任何切片或者函数式的解决方案？

Answer 1

>>> from itertools import combinations
>>> lst = [10, 13, 15, 18, 20, 15]
>>> count = 0
>>> for x, y in combinations(lst, 2):
        if x + y == 30:
            print(x, y)
            count += 1

10 20
15 15

>>> print(count)
2

Answer 2

您可以使用 itetools.combinations and a generator expression within sum :

>>> my_list=[10, 13, 15, 18, 20, 15]
>>> from itertools import combinations
>>> sum(i+j==30 for i,j in combinations(my_list,2))
2

如果你也想要那些项目，你可以使用列表理解：

>>> [(i,j) for i,j in combinations(my_list,2) if i+j==30]
[(10, 20), (15, 15)]

Answer 3

或者，如果您不想使用 itertools，您可以使用以下列表推导式

 len([(ii,jj) for i, ii in enumerate(a) for j, jj in enumerate(a[i+1:]) if ii+jj==30])

这给了你

 len([(10, 20), (15, 15)]) = 2

组合方法的运行时间约为一半。

Answer 4

由于这是一个编程挑战，这里有一个列表长度具有线性复杂度的解决方案（使用组合会使您的复杂度达到二次方）：

from collections import defaultdict
def count_pairs_summing_to(lst, n):  
    element_counter = defaultdict(int)
    count = 0
    for x in lst:
        if (n - x) in element_counter:
            count += element_counter[n - x]
        element_counter[x] += 1
    return count

我们的想法是一次传递数据并跟踪我们之前在散列中看到的元素 table。当我们看到一个新元素x时，我们只需要知道我们之前是否见过30 - x。
我们还跟踪我们看到每个元素的次数以确保我们计算重复对（例如 count_pairs_summing_to([10, 10, 20, 25], 30) 应该 return 2.）。

一些基准测试：

lst = [10, 13, 15, 18, 20, 15]

%timeit sum(i+j==30 for i,j in combinations(lst,2))
100000 loops, best of 3: 3.35 µs per loop

%timeit len([(ii,jj) for i, ii in enumerate(lst) for j, jj in enumerate(lst[i+1:]) if ii+jj==30])
100000 loops, best of 3: 6.59 µs per loop

%timeit count_pairs_summing_to(lst, 30)
100000 loops, best of 3: 2.92 µs per loop

# With a slightly bigger list.
import numpy.random as random
big_lst = list(random.randint(0, 100, size=1000))

%timeit len([(ii,jj) for i, ii in enumerate(big_lst) for j, jj in enumerate(big_lst[i+1:]) if ii+jj==30])
10 loops, best of 3: 125 ms per loop

%timeit sum(i+j==30 for i,j in combinations(big_lst,2))
1 loops, best of 3: 1.21 s per loop

# The previous one was surprisingly slow but it can be fixed:
%timeit sum(1 for i,j in combinations(big_lst,2) if i+j==30)
1 loops, best of 3: 88.2 ms per loop

%timeit count_pairs_summing_to(big_lst, 30)
1000 loops, best of 3: 504 µs per loop

如何迭代列表中的每个元素并将其与另一个元素相加以找到一个数字？

How to iterate and sum each element in a list with another to find a number?

python

algorithm

python-2.7

data-structures

itertools