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