你将如何使用哈希映射而不是集合来解决这个问题？

Question

def pair_sum(array,r_sum):
  if len(array)<2:
    return
  found = set()
  output= set()
  for num in array:
    k = r_sum - num
    if k not in found:
      found.add(num)
    else:
      output.add(((min(num,k)),(max((num,k)))))
  print('\n'.join(map(str,list(output))))

所以对于这个问题，如果我有一个数组，例如 [4,1,2,5,3]，目标和为 6，函数将 return 两对数字相加到目标总和，所以在这种情况下，它将 return (1,5) 和 (2,4)。我如何使用散列映射而不是集合来做类似的事情？

Answer 1

您希望使用 hash map 而不是 set 显然是因为想要将运行时间从 O(n^2) 减少到 O(n)，其中 n 是 array.

的长度

这是使用 python 字典（哈希映射）的 O(n) 实现。

array = [4, 1, 2, 5, 3]
r_sum = 6

found = {}
while array:
    num = array.pop(0)
    k = r_sum - num
    if k in found:
        found[k] = True
    else:
        found[num] = False

for key, val in found.items():
    if val:
        print("({}, {})".format(key, r_sum - key))

你将如何使用哈希映射而不是集合来解决这个问题？

How would you solve this problem using a hash map instead of a set?

python

arrays

algorithm

hashmap

set