3对已排序的数组进行排序。 O（NlogN）实现

Question

给定n个元素的SORTED数组。从数组中找出三个数字，它们将加起来给定数字k。

下面是我一直想到现在： 我们从两个变量L和H开始，它们存储数组中第一个元素和最后一个元素的索引。在这些索引处添加元素，并从k中减去它并将其存储在一个变量中，比如z。 现在，由于数组已排序，我可以在数组中进行二进制搜索。如果发现z，我有三个数字。如果z没有找到，我不得不增加L或递减H.

现在我不知道何时增加L或何时递减H. 任何想法？

Answer 1

https://en.wikipedia.org/wiki/3SUM

计算机科学未解决的问题：是否有一个算法解决3SUM问题及时O(n^(2-e))一些e > 0？

另一句名言：

目前最有名的算法3SUM在O(n^2/(log n/log log n))时间

运行，因此没有已知的O(nlogn)算法针对此问题。维基百科二次算法：

sort(S); 
for i=0 to n-3 do 
    a = S[i]; 
    start = i+1; 
    end = n-1; 
    while (start < end) do 
     b = S[start] 
     c = S[end]; 
     if (a+b+c == 0) then 
      output a, b, c; 
      // Continue search for all triplet combinations summing to zero. 
      end = end - 1 
     else if (a+b+c > 0) then 
      end = end - 1; 
     else 
      start = start + 1; 
     end 
    end 
end