查看“︁3SUM”︁的源代码

{{unsolved|計算機科學|是否存在一个算法，能够在<math>O(n^{2-\epsilon})</math> （<math>\epsilon>0</math>）的时间复杂度内解决3SUM问题？}}
在[[计算复杂度理论]]中, '''3SUM'''问题是指如下的问题：给定一个包含n个实数的集合，判断其中是否包含3个和为0的元素。问题也可以推广到一个更一般化的版本，rSUM，是要求判断集合中是否存在r个数的和为0。3SUM问题可以很容易地在<math>O(n^2)</math>的时间复杂度内解决。对于某些特化的计算模型，这已经达到了它们<math>\Omega(n^{\lceil r/2 \rceil})</math>的复杂度下界。

人们曾经猜想任何3SUM问题的确定性算法都至少需要<math> \Omega(n^2) </math>的时间复杂度。然而在2014年，最初的3SUM被Allan Grønlund和Seth Pettie否决了。他们给出了一个能在能在<math>O(n^2 / ({\log n} / {\log \log n})^{2/3})</math>的时间复杂度内求解3SUM问题的确定性算法。<ref>{{Cite conference|doi=10.1109/FOCS.2014.72|title=Threesomes, Degenerates, and Love Triangles|conference=2014 IEEE 55th Annual Symposium on Foundations of Computer Science|pages=621|year=2014|last1=Gronlund|first1=A.|last2=Pettie|first2=S.|isbn=978-1-4799-6517-5}}</ref>目前仍然有人猜想3SUM是不可能在<math>O(n^{2-\Omega(1)})</math>的时间复杂度内解决的。

==二次时间复杂度算法==

设输入数据存储与数组<math>S[0..n-1]</math>，3SUM问题可以通过[[散列表]]在平均<math>O(n^2)</math>的时间复杂度内解决。方法是先将S中的元素全部插入到一个散列表中，然后对于每一个数组下标对<math>(i, j)</math>，检查<math>-(S[i]+S[j])</math>是否在散列表中即可。

一个更好的方法是，先将输入数据排序，然后用一种巧妙的方法测试所有可能的输入组合，而避免使用[[二分查找]]。这种办法即使在最坏情况下也可以保证<math>O(n^2)</math>的时间复杂度，它的伪代码如下所示：<ref>[http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf Visibility Graphs and 3-Sum] {{Wayback|url=http://www.ti.inf.ethz.ch/ew/courses/CG09/materials/v12.pdf |date=20201212195444 }} by Michael Hoffmann</ref>
  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'''的当前值以红色标记。
  <span style="color:green">-25</span> <span style="color:red">-10</span> -7 -3 2 4 8 <span style="color:red">10</span>  (a+b+c==-25)
  <span style="color:green">-25</span> -10 <span style="color:red">-7</span> -3 2 4 8 <span style="color:red">10</span>  (a+b+c==-22)
  . . .
  <span style="color:green">-25</span> -10 -7 -3 2 4 <span style="color:red">8</span> <span style="color:red">10</span>  (a+b+c==-7)
  -25 <span style="color:green">-10</span> <span style="color:red">-7</span> -3 2 4 8 <span style="color:red">10</span>  (a+b+c==-7)
  -25 <span style="color:green">-10</span> -7 <span style="color:red">-3</span> 2 4 8 <span style="color:red">10</span>  (a+b+c==-3)
  -25 <span style="color:green">-10</span> -7 -3 <span style="color:red">2</span> 4 8 <span style="color:red">10</span>  (a+b+c==2)
  -25 <span style="color:green">-10</span> -7 -3 <span style="color:red">2</span> 4 <span style="color:red">8</span> 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，找出三个数{{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}使得{{tmath|a+b+c{{=}}0}}。下文记单集合的3SUM问题为3SUM&times;1，三集合的3SUM问题为3SUM&times;3，则3SUM&times;3按下列步骤即可转化为3SUM&times;1：
* 对''X''、''Y''、''Z''集合中所有元素，取{{tmath|X[i] \gets X[i]*10+1}}，{{tmath|Y[i] \gets Y[i]*10+2}}，{{tmath|Z[i] \gets Z[i]*10-3}}；
* 令''S''为''X''、''Y''、''Z''的并集；
* 用3SUM&times;1的解法求出满足{{tmath|a' \in S,\ b' \in S,\ c' \in S}}且{{tmath|a'+b'+c'{{=}}0}}的三个元素；
* 因为总和的LSD（least significant digit，最低位）为零，故{{mvar|a', b', c'}}的LSD一定为1、2、7（不一定按顺序）。不失一般性，设{{mvar|a', b', c'}}的LSD分别为1、2、7；
* 最终解即为{{tmath|a \gets (a'-1)/10,\ b \gets (b'-2)/10,\ c \gets (c'+3)/10}}。
根据第一步中的变换，一定有{{math|''a''∈''X'', ''b''∈''Y'', ''c''∈''Z''}}。<ref>For a reduction in the other direction, see [http://cs.stackexchange.com/questions/37888/variants-of-the-3-sum-problem Variants of the 3-sum problem] {{Wayback|url=http://cs.stackexchange.com/questions/37888/variants-of-the-3-sum-problem |date=20150205141919 }}.</ref>


== 参考资料 ==
{{reflist}}

[[Category:計算幾何]]
[[Category:多项式时间问题]]