2.10 如何从数组中找出满足a+b=c+d的两个数对

【出自YMX面试题】

难度系数：★★★☆☆

被考察系数：★★★★☆

题目描述：

给定一个数组，找出数组中是否有两个数对（a, b）和（c, d），使得a+b=c+d，其中a、b、c和d是不同的元素。如果有多个答案，打印任意一个即可。例如，给定数组：{3, 4, 7, 10, 20, 9, 8}，可以找到两个数对（3, 8）和（4, 7），使得3+8=4+7。

分析与解答：

最简单的方法就是使用四重遍历，对所有可能的数对，判断是否满足题目要求，如果满足则打印出来，但是这种方法的时间复杂度为O（N^4），很显然不满足要求。下面介绍另外一种方法——Hash法，算法的主要思路：以数对为单位进行遍历，在遍历过程中，把数对和数对的值存储在哈希表中（键为数对的和，值为数对）。当遍历到一个键值对，如果它的和在哈希表中已经存在，那么就找到了满足条件的键值对。下面使用HashMap为例，实现代码如下：

程序的运行结果为

算法性能分析：

这种方法的时间复杂度为O（N2）。因为使用了双重循环，而HashMap的插入与查找操作实际的时间复杂度为O（1）。