python - 使用 python 重复条目求和到 K

Question

我正在尝试准备一个重复的面试问题。给定一个数组，找到对以得到它们的总和作为 k。在这种情况下，我使用 python 字典而不是排序方法。代码如下:

def sumToK(lst):
  k = 16  # <- define the k here
  d = {} # build a dictionary 

  # build the hashmap key = val of lst, value = i
  for index, val in enumerate(lst):
    d[val] = index

# find the key; if a key is in the dict, and not the same index as the current key
for i, val in enumerate(lst):
  if (k-val) in d and d[k-val] != i:
    print k-val, val

a = [1,4,45,6,10,12,3]
sumToK(a)

我以上述方式得到了重复的值。我怎样才能避免它？另外，如果数组包含重复值怎么办。例如 a = [1,4,45,6,10,12,4,8,8] 谢谢。

Answer 1

你做的工作太多了。您根本不需要跟踪索引，您可以一次性完成。只需保留集合您到目前为止看到的所有数字，对于每个新数字n，您可以检查它的对(k - n) 已经在你的集合中:

def find_pairs(numbers, k):
    seen = set()
    for n in numbers:
        if k - n in seen:
            print n, k - n
        seen.add(n)

a = [1,4,45,6,10,12,3]
find_pairs(a, 16)
# 10 6
# 12 4

如果您想防止打印重复对，您可以更改条件以确保 n not in seen。