2.10 如何從數(shù)組中找出滿足a+b=c+d的兩個數(shù)對

【出自YMX面試題】

難度系數(shù)：★★★☆☆

被考察系數(shù)：★★★★☆

題目描述：

給定一個數(shù)組，找出數(shù)組中是否有兩個數(shù)對（a, b）和（c, d），使得a+b=c+d，其中a、b、c和d是不同的元素。如果有多個答案，打印任意一個即可。例如，給定數(shù)組：{3, 4, 7, 10, 20, 9, 8}，可以找到兩個數(shù)對（3, 8）和（4, 7），使得3+8=4+7。

分析與解答：

最簡單的方法就是使用四重遍歷，對所有可能的數(shù)對，判斷是否滿足題目要求，如果滿足則打印出來，但是這種方法的時間復雜度為O（N^4），很顯然不滿足要求。下面介紹另外一種方法——Hash法，算法的主要思路：以數(shù)對為單位進行遍歷，在遍歷過程中，把數(shù)對和數(shù)對的值存儲在哈希表中（鍵為數(shù)對的和，值為數(shù)對）。當遍歷到一個鍵值對，如果它的和在哈希表中已經(jīng)存在，那么就找到了滿足條件的鍵值對。下面使用HashMap為例，實現(xiàn)代碼如下：

程序的運行結(jié)果為

算法性能分析：

這種方法的時間復雜度為O（N2）。因為使用了雙重循環(huán)，而HashMap的插入與查找操作實際的時間復雜度為O（1）。