给\(n\)个数字(\(n < 2*10^5\)),他们的大小在\([1,2.5*10^6]\).
在其中找\(4\)个数字,他们符合\(a+b=c+d\).
首先用一个大小\(2.5*10^6\)的数组,记录每个数字出现的次数.
如果出现次数大于\(2\)的数字有两个或以上,那么他们就是答案.
如果有一个数字出现次数在四次或以上,那么他也是答案.
转换式子
所以找到两对数字\((a,d)\)和\((c,b)\),他们之间的差相等.
显然他们是\(a\leq d\leq c \leq b\)的.
将所给的数字排序,求出他们相邻之间的差,得到\(n-1\)个数字.像这样
1 2 2 4 5 7 ->
1 0 2 1 1
也用一个大小为\(2.5*10^6\)的数组,记录得到的这\(n-1\)个差出现的次数.
如果找到一个差,出现两次以上,那么就说明我们找到了这两对差值相同的数字.
根据这个差值去扫描一次排序后的数字,就能找到这两对数字了.
但是你找到的这两对数字\((a,d)\)和\((c,b)\),可能\(d\)和\(c\)是同一个数字.就像这样
1 2 3 ->
1 1
这样就只能看下面一种情况了.
如果他们完全不满足以上的情况.那么说明只给了不超过\(n<2*10^3\)个数字.
为什么?
如果要满足相邻数字之间的差各不相同,那就要有\(n-1\)个不同的差.
所以给的数字里面最大的一个数字至少是\(n-1\)个不同的差的和.
这个最大数字不超过\(2.5*10^6\),可见\(n\)的数量很小.
既然数字则么少,可以用两趟循环随便找,也不会超过时间限制.
原文：https://www.cnblogs.com/zzidun-pavo/p/14530263.html