algorithm - 查找数组中总和为指定值的所有整数对

Question

Design an algorithm to find all pairs of integers within an array which sum to a specified value.

我已经尝试过使用哈希表来存储数组元素总和的条目来解决这个问题，但这不是一个有效的解决方案。

我可以使用什么算法来有效地解决这个问题？

Answer 1

我不明白为什么哈希表方法效率低下，至少在算法分析方面是这样——诚然，在内存局部性方面，它可能非常糟糕。不管怎样，扫描数组两次...

第一次扫描 - 将所有数组元素放入哈希表 - 总共 O(n)。单个插入仅摊销 O(1)，但关于摊销分析如何工作的一件巧妙的事情意味着 O(n) 是绝对的 - 不摊销。

第二次扫描 - 检查哈希表中的(总和 - 当前) - O(n) 总计。

至少在理论上，这优于 O(n log n) 排序和搜索方法。

然后，请注意，您可以将两个扫描合并为一个。在第一次扫描过程中，一旦遇到第二对，就可以发现一对。在伪代码中...

for i in array.range
  hashset.insert (array [i])

  diff = sum - array [i]
  if hashset.includes (diff)
    output diff, array [i]

如果您需要项目的位置，请使用 HashMap 并将项目位置存储在其中。如果您需要处理重复项，您可能需要将计数存储在 HashMap 中。对于位置和重复项，您可能需要位置链接列表的起始指针散列图。

这对哈希表的实现做出了假设，但考虑到大多数当前语言和库中的通常实现，这些假设是相当安全的。

顺便说一句 - 结合扫描不应被视为优化。迭代开销应该是微不足道的。对于非常大的数组，内存局部性问题可能会使单次传递的效率稍微提高一些，但无论如何，真正的内存局部性问题将出现在哈希表查找中。

IMO 合并扫描的唯一真正原因是因为您只希望每对报告一次 - 在两次扫描方法中处理它会更麻烦一些。