python - 防止在 Python 中的迭代期间使用值的倒数

Question

我得到了一个包含 n 个整数的数组和一个数字 k。我发现数组中是否有一对元素的总和恰好为 k。例如，给定数组 [1, 3, 7] 和 k = 8，答案是肯定的，但给定 k = 6 答案是否定的。

我的第一个尝试是使用蛮力方法。我有一个不错的算法，可以完成工作而不用担心效率。

arr = [1,3,7]

for i in range(len(arr)):
    for a in range(len(arr)):
        if i != a:
            if arr[i] + arr[a] == 8:
                print('{} and {} is: yes'.format(arr[i], arr[a]))

            elif arr[i] + arr[a] == 6:
                print('{} and {} is: no'.format(arr[i], arr[a]))

输出如下:

1 and 7 is: yes
7 and 1 is: yes

显然我不希望显示相反的大小写 arr[0] + arr[2] 和 arr[2] + arr[0]。我尝试在输出循环中为 arr[i] 使用数组 pop 和 del。

如何告诉 python 忽略相反的大小写？

Answer 1

你可以改变:

for a in range(len(arr)):

到

for a in range(i+1,len(arr)):

这只会在 i < a 时测试用例，所以会找到 arr[0]+arr[2]，但不会尝试相反的情况。

一种更快的方法是将每个项目添加到一个集合中，然后查看集合中是否存在 8-arr[i]。这将是 O(n) 而不是 O(n^2)