
_START_ARTICLE_
3SUM
_START_SECTION_
二次时间复杂度算法
_START_PARAGRAPH_
设输入数据存储与数组，3SUM问题可以通过散列表在平均的时间复杂度内解决。方法是先将S中的元素全部插入到一个散列表中，然后对于每一个数组下标对，检查是否在散列表中即可。_NEWLINE_一个更好的方法是，先将输入数据排序，然后用一种巧妙的方法测试所有可能的输入组合，而避免使用二分查找。这种办法即使在最坏情况下也可以保证的时间复杂度，它的伪代码如下所示：_NEWLINE__NEWLINE_ sort(S);_NEWLINE_ for i=0 to n-3 do_NEWLINE_    a = S[i];_NEWLINE_    start = i+1;_NEWLINE_    end = n-1;_NEWLINE_    while (start < end) do_NEWLINE_       b = S[start]_NEWLINE_       c = S[end];_NEWLINE_       if (a+b+c == 0) then_NEWLINE_          output a, b, c;_NEWLINE_          // Continue search for all triplet combinations summing to zero._NEWLINE_           end = end - 1_NEWLINE_       else if (a+b+c > 0) then_NEWLINE_          end = end - 1;_NEWLINE_       else_NEWLINE_          start = start + 1;_NEWLINE_       end_NEWLINE_    end_NEWLINE_ end_NEWLINE_下面的例子展示了算法在一个较小的数组上是如何执行的。变量a的当前值以绿色标记，而b和c的当前值以红色标记。_NEWLINE__NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==-25)_NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==-22)_NEWLINE_ . . ._NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)_NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==-7)_NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==-3)_NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==2)_NEWLINE_ -25 -10 -7 -3 2 4 8 10  (a+b+c==0)_NEWLINE_我们可以从上面的过程中看出这个算法为什么是正确的。假设3SUM问题有一组解a + b + c = 0。首先单向移动的最左侧下标必然会到达a，而之后剩下的两个下标会有一个先遇到b或者c，而根据a+b+c > 0时移动右侧下标，反之移动左侧下标的规则，在此之后先遇到的下标会保持不动，知道我们移动另外一个下标找到对应的那一组解为止。因此对于3SUM问题的任意一个解最终都会被这个算法发现。