折半枚举(双向搜索)

4 values whose sum is 0

给定各有n个整数的四个数列A,B,C,D。要从每个数列中各取出1个数,使四个数的和为0。求出这样的组合的个数。当一个数列中有多个相同的数字时,把它们作为不同的数字看待。
输入:n=6
A={-45, -41, -36, -36, 26, -32};
B={22 ,-27 ,53 ,30 ,-38 ,-54};
C={42 ,56 ,-37, 75, -10, -6};
D={-16 ,30, 77, -46, 62, 45};
输出:
5(-45-27+42+30=0,26+30-10-46=0,-32+22+56-46=0,-32+30-75+77=0, -32-54+56+30=0)

最简单的思路是n^4遍历,但是这显然是不科学的!
那么科学的方法是怎样呢?
我们先从数组C和数组D取出不同的c,d组合一下,得到n^2个a+b的组合构成数组CD,将这些和排好序,然后就可以遍历A,B利用二分搜索,使得复杂度变为n^2logn.
注意:因为这个题中将值相等的数字看作不同的数字,所以我们要将同一个值的重复次数也算到里面去。
折半枚举(双向搜索)