跳至內容

3SUM

維基百科,自由的百科全書

計算複雜度理論中, 3SUM問題是指如下的問題:給定一個包含n個實數的集合,判斷其中是否包含3個和為0的元素。問題也可以推廣到一個更一般化的版本,rSUM,是要求判斷集合中是否存在r個數的和為0。3SUM問題可以很容易地在的時間複雜度內解決。對於某些特化的計算模型,這已經達到了它們的複雜度下界。

人們曾經猜想任何3SUM問題的確定性算法都至少需要的時間複雜度。然而在2014年,最初的3SUM被Allan Grønlund和Seth Pettie否決了。他們給出了一個能在能在的時間複雜度內求解3SUM問題的確定性算法。[1]目前仍然有人猜想3SUM是不可能在的時間複雜度內解決的。

二次時間複雜度算法

設輸入數據存儲與數組,3SUM問題可以通過散列表在平均的時間複雜度內解決。方法是先將S中的元素全部插入到一個散列表中,然後對於每一個數組下標對,檢查是否在散列表中即可。

一個更好的方法是,先將輸入數據排序,然後用一種巧妙的方法測試所有可能的輸入組合,而避免使用二分查找。這種辦法即使在最壞情況下也可以保證的時間複雜度,它的偽代碼如下所示:[2]

 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

下面的例子展示了算法在一個較小的數組上是如何執行的。變量a的當前值以綠色標記,而bc的當前值以紅色標記。

 -25 -10 -7 -3 2 4 8 10  (a+b+c==-25)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)
 . . .
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==2)
 -25 -10 -7 -3 2 4 8 10  (a+b+c==0)

我們可以從上面的過程中看出這個算法為什麼是正確的。假設3SUM問題有一組解a + b + c = 0。首先單向移動的最左側下標必然會到達a,而之後剩下的兩個下標會有一個先遇到b或者c,而根據a+b+c > 0時移動右側下標,反之移動左側下標的規則,在此之後先遇到的下標會保持不動,直到我們移動另外一個下標找到對應的那一組解為止。因此對於3SUM問題的任意一個解最終都會被這個算法發現。

變體

總和非零

用下列方法可以搜索出集合中和為任意常數C的三個元素:

  • 將集合中每個元素分別減去C/3;
  • 對新集合使用3SUM算法求解。

三個不同數組

我們也能從三個整數集合中分別找出一個元素使其和為零,即對於給定的三個整數集合X、Y、Z,找出三個數aX, bY, cZ使得。下文記單集合的3SUM問題為3SUM×1,三集合的3SUM問題為3SUM×3,則3SUM×3按下列步驟即可轉化為3SUM×1:

  • XYZ集合中所有元素,取
  • SXYZ的併集;
  • 用3SUM×1的解法求出滿足的三個元素;
  • 因為總和的LSD(least significant digit,最低位)為零,故a', b', c'的LSD一定為1、2、7(不一定按順序)。不失一般性,設a', b', c'的LSD分別為1、2、7;
  • 最終解即為

根據第一步中的變換,一定有aX, bY, cZ[3]


參考資料

  1. ^ Gronlund, A.; Pettie, S. Threesomes, Degenerates, and Love Triangles. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science: 621. 2014. ISBN 978-1-4799-6517-5. doi:10.1109/FOCS.2014.72. 
  2. ^ Visibility Graphs and 3-Sum頁面存檔備份,存於互聯網檔案館) by Michael Hoffmann
  3. ^ For a reduction in the other direction, see Variants of the 3-sum problem頁面存檔備份,存於互聯網檔案館).