2-sum 和 3-sum 问题的快速解法

用科学方法分析程序中介绍了 3-sum 问题的暴力解法（ThreeSum）——用三个嵌套的 for 循环来求和为 0 的三元组个数，增长数量级为立方级别。

类似地，对于 2-sum 问题（找出一个输入中所有和为 0 的整数对的数量），可用两个嵌套的 for 循环来解决（TwoSum），增长数量级为平方级别。

将输入数据排序后应用二分查找，可得到 2-sum 的快速解法（假设输入的所有整数均各不相同）：

首先将数组排序（为二分查找做准备），然后对于数组中的每个 a[i]，使用 BinarySearch 的 rank() 方法对 -a[i] 进行二分查找。如果结果为 j 且 j>i^[1]，我们就将计数器加 1。

归并排序所需的时间和 NlogN 成正比，二分查找所需的时间和 logN 成正比，因此整个算法的运行时间和 NlogN 成正比。

2-sum 问题的线性对数级别的解法

和刚才一样，我们假设所有整数均各不相同。当且仅当 -(a[i] +a[j]) 在数组中时，整数对（a[i] 和 a[j]）为某个和为 0 的三元组的一部分。下面代码框中的代码会将数组排序并进行 N(N-1)/2 次二分查找^[2]，每次查找所需的时间都和 logN 成正比。因此总运行时间和 N²logN 成正比。

3-sum 问题的 N²lgN 解法

图 1 显示了用这 4 种算法的成本的悬殊差距。

图 1 解决 2-sum 和 3-sum 问题的各种算法的成本

下界

我们还能找到比 2-sum 问题的 TwoSumFast 和 3-sum 问题的 ThreeSumFast 快得多的算法吗？是否存在解决 2-sum 问题的线性级别的算法，3-sum 问题的线性对数级别的算法？对于 2-sum，这个问题的回答是没有（在仅允许在线性或是平方级别计算或比较这些整数的成本模型下）；对于 3-sum，回答是不知道，不过专家们相信 3-sum 可能的最优算法是平方级别的。

为算法在最坏情况下的运行时间给出一个下界的思想是非常有意义的，它非常有助于指引我们追求更加有效的算法。