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

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

给定一个数组，找出数组中是否有两个数对（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⁴），很显然算法效率太低，不满足题目要求。

下面介绍另外一种方法—Hash法，该方法的主要思路为：以数对为单位进行遍历，在遍历过程中，把数对和数对的值存储在哈希表中（键为数对的和，值为数对），当遍历到一个键值对，如果它的和在哈希表中已经存在，那么就找到了满足条件的键值对。

下面使用HashMap为例给出实现代码：

程序的运行结果为

算法性能分析：

因为算法使用了双重循环，所以这个算法的时间复杂度为O（n²）。而 HashMap 的插入与查找操作实际的时间复杂度为O（1）。