问题：给定n个整数的数组S，S中是否有元素a、b、c和d，使得a+b+c+d=target找到数组中所有唯一的四胞胎，它们给出目标的总和。
注：
四胞胎（A、B、C、D）中的元素必须按非降序排列。（即a≤b≤c≤d）
解决方案集不能包含重复的四胞胎。
例如，给定数组S={10-10-2 2}，而target=0。
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
我知道这个问题有一个o（n^3）解，但我想知道是否有一个更快的算法。我搜索了很多，发现很多人给出了一个o（n^2logn）的解决方案，当s中有对和的重复时（比如here
以及here）我希望有人能给我一个正确版本的O（n^ 2Logn）算法，如果它真的存在。
谢谢！
最佳答案
蛮力算法需要时间o（n^4）：使用四个嵌套循环从输入中形成四个项的所有组合，并将任意和保留到目标。
一个简单的改进需要时间o（n^3）：使用三个嵌套循环来形成来自输入的三个项的所有组合，并将任何一个和保持为目标的负数。
我知道的最好的算法是中间相遇算法，它在时间o（n^2）内运行：使用两个嵌套循环形成输入中两个项的所有组合，将成对和总计存储在某种按total索引的字典（哈希表、平衡树）中。然后再使用两个嵌套循环来再次形成输入中两个项的所有组合，并保留嵌套循环中的两个项，加上字典中的两个项，对于字典中总和为负数的任何一对项。
我在my blog有代码。
关于arrays - Leetcode:四和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25142170/