计数数组中的元素对，这些元素的和等于给定的和(但)在一次迭代中完成(！)

Question

给定一个整数数组和一个数字"sum"，在SINGLE迭代中查找数组中其和等于给定"sum’的整数对的数量。(O(n(时间复杂性是不够的！(。

通常，我会在数组中迭代两次，一次创建频率的哈希图，另一次查找对的数量，如下所示

def getPairsCount(arr, n, sum): 
m=defaultdict(int)      
for i in range(0, n): #iteration NO. 1

m[arr[i]] += 1
twice_count = 0 
for i in range(0, n): #iteration NO. 2

twice_count += m[sum - arr[i]] 
if (sum - arr[i] == arr[i]): 
twice_count -= 1
return int(twice_count / 2) 

面试官要求我在一次迭代中做同样的事情，而不是两次。我不知道如何在边缘情况下做到这一点，比如{2,2,1,1}，其中所需的和是3。

Answer 1

一种方法是在使用哈希图的同时构建哈希图(从而只循环列表一次(。因此，对于数组中的每个值，请检查您以前是否看到过补码(sum所需的值(。如果是这样的话，你就知道你有了一个新的对，你就从看到的值中删除了补码。否则，您没有一个和，您将刚才看到的值相加。

在代码中，这看起来如下：

from collections import defaultdict
def get_pairs_count(array, sum): 
pairs_count = 0
seen_values = defaultdict(int)

for value in array:
complement = sum - value
if seen_values[complement] > 0:
pairs_count += 1
seen_values[complement] -= 1
else:
seen_values[value] += 1

return pairs_count

Answer 2

另一种方式：

def pair_sum2(arr, k):
if len(arr)<2:
return
seen=set()
output=set()
for num in arr:
target=k-num
print("target",target)
if target not in seen:
print("seen before add",seen)
seen.add(num)
print("seen",seen)
else:
output.add( (min(num, target), max(num, target)) )
print("op:",output)
print ('n'.join( map(str, list(output)) ) )