3SUM

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

人們曾經猜想任何3SUM問題的確定性算法都至少需要$\Omega (n^{2})$的時間複雜度。然而在2014年，最初的3SUM被Allan Grønlund和Seth Pettie否決了。他們給出了一個能在能在$O(n^{2}/({\log n}/{\log \log n})^{2/3})$的時間複雜度內求解3SUM問題的確定性算法。目前仍然有人猜想3SUM是不可能在$O(n^{2-\Omega (1)})$的時間複雜度內解決的。

二次時間複雜度算法

設輸入數據存儲與數組$S[0..n-1]$，3SUM問題可以通過散列表在平均$O(n^{2})$的時間複雜度內解決。方法是先將S中的元素全部插入到一個散列表中，然後對於每一個數組下標對$(i,j)$，檢查$-(S[i]+S[j])$是否在散列表中即可。

一個更好的方法是，先將輸入數據排序，然後用一種巧妙的方法測試所有可能的輸入組合，而避免使用二分查找。這種辦法即使在最壞情況下也可以保證$O(n^{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的當前值以綠色標記，而b和c的當前值以紅色標記。

 -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，找出三個數a∈X, b∈Y, c∈Z使得$a+b+c=0$。下文記單集合的3SUM問題為3SUM×1，三集合的3SUM問題為3SUM×3，則3SUM×3按下列步驟即可轉化為3SUM×1：

• 對X、Y、Z集合中所有元素，取$X[i]\gets X[i]*10+1$，$Y[i]\gets Y[i]*10+2$，$Z[i]\gets Z[i]*10-3$；
• 令S為X、Y、Z的併集；
• 用3SUM×1的解法求出滿足$a'\in S,\ b'\in S,\ c'\in S$且$a'+b'+c'=0$的三個元素；
• 因為總和的LSD（least significant digit，最低位）為零，故a', b', c'的LSD一定為1、2、7（不一定按順序）。不失一般性，設a', b', c'的LSD分別為1、2、7；
• 最終解即為$a\gets (a'-1)/10,\ b\gets (b'-2)/10,\ c\gets (c'+3)/10$。

根據第一步中的變換，一定有a∈X, b∈Y, c∈Z。