直到做了这次采访，我才意识到3SUM可以比N²更快地完成。

“Threesomes, Degenerates, and Love Triangles”，2014年的论文，更多细节请见：https://t.co/2AYc6rBgRb

@rrwilliams 在片段和播客中解释了一些高层次方法：https://t.co/oSEyDt9GVy

Threesomes, Degenerates, and Love Triangles

来源：https://arxiv.org/abs/1404.0799 查看PDF (https://arxiv.org/pdf/1404.0799)

摘要：3SUM问题是要判断给定一个包含n个实数的集合，是否存在三个数之和为零。广泛推测一个平凡的O(n^2)时间算法是最优的，多年来这一推测的后果已被揭示。这个3SUM猜想意味着计算几何中许多问题的\Omega(n^2)下界，而该猜想的一个变体则意味着三角形枚举、动态图算法和字符串匹配数据结构中的强下界。在本文中，我们反驳了3SUM猜想。我们证明了3SUM的决策树复杂度为O(n^{3/2}\sqrt{\log n})，并给出了两个次二次的3SUM算法：一个确定性算法运行时间为O(n^2 / (\log n/\log\log n)^{2/3})，另一个随机算法以高概率在O(n^2 (\log\log n)^2 / \log n)时间内运行。我们的结果直接导致所有奇数k\ge 3的k元线性退化测试的界得到改进。该问题是要判断给定一个线性函数f(x_1,\ldots,x_k) = \alpha_0 + \sum_{1\le i\le k} \alpha_i x_i和一个集合A \subset \mathbb{R}，是否0\in f(A^k)。我们证明了这个问题的决策树复杂度为O(n^{k/2}\sqrt{\log n})。最后，我们针对实值矩阵的(\min,+)-乘积的一个推广给出了一个次立方算法，并将其应用于加权图中寻找零权三角形的问题。我们给出了这个问题的深度为O(n^{5/2}\sqrt{\log n})的决策树，以及一个运行时间为O(n^3 (\log\log n)^2/\log n)的算法。

提交历史

来自：Seth Pettie 发送电子邮件 [v1] 2014年4月3日星期四 08:30:03 UTC (17 KB) [v2] 2014年5月29日星期四 10:02:28 UTC (57 KB) [v3] 2014年5月30日星期五 19:46:20 UTC (57 KB)

Ryan Peterman (@ryanlpeterman): Ryan Williams (@rrwilliams) 是麻省理工学院的教授，也是理论计算机科学哥德尔奖得主。我采访了他，内容涵盖他的工作，首先从一个流行的Leetcode问题（3 SUM）开始。

在本集中：

• 比流行解法更快地解决Leetcode问题