数组中两个元素之差为目标数k的对个数是多少?蛮力是微不足道的，从每个指数开始，并通过所有即将到来的指数。我需要在O(n)内完成。我知道用哈希表是可以做到的，但是我听不懂。
的例子:(2、5、4、1、7,4],k = 3这里有5双。(2,5)， (4,1)， (4,7)， (1,4)， (7,4)
我将这个问题定义为一个比Leetcode的Subarray Sum Equals k更简单的问题。我认为Leetcode问题具有相同的解决方案，除了它将应用于运行的Sum数组。
您可以构建一个字典，将数字的每个实例与其n-k值关联起来。复杂度是0 (n)然后遍历这些数字，并将它们与字典中相应的数字列表配对(也在O(n)中):
numbers = [2,5,4,1,7,4]
k=3
numSet = dict()
for n in numbers: numSet.setdefault(n-k,[]).append(n) # O(n)
pairs = [(n,m) for n in numbers for m in numSet.get(n,[])] #O(n)
print(pairs)
[(2, 5), (1, 4), (4, 7), (4, 7)]
考虑到数字可以在列表中重复，实际复杂度可能大于O(n)，因为第二部分可能产生超过n对(例如[3,6,3,6,3,6]产生9对)。在O(n)中产生超过n的结果在技术上是不可能的，但我猜提供的数据是为了避免这些极端情况而设计的。