arrays - 在数组中找到三元组，使得两个数字的总和也是给定数组中的数字

Question

给定一个数组，例如 [1, 0, -1, 2, 3, 4, 5]，找到所有长度为 3 的子集，其中一个元素等于另一个元素的总和子集中的两个元素。例如:

1 + -1 == 0 (from [1, 0, -1])
2 +  3 == 5 (from [2, 3, 5])

我提出了一个O(n²) 的解决方案，但我的面试官坚持认为有一个O(n log n) 的解决方案。

解决这个问题的最佳方法是什么？

Answer 1

乍一看，我看不出有小于O(n²)的算法。 (除非是特别聪明的)

这个问题与臭名昭著的 3SUM 问题非常相似:基本上，这个想法是给定一组 n 个元素，是否存在总和为零的三元组？

求解 3SUM 的算法比 O(n²) 还未知 - 这是计算机科学中的一个开放问题...(参见此处:http://en.wikipedia.org/wiki/3SUM)

但是，由于您的问题不完全是 3SUM (A+B+C=0)，而是涉及 (A+B=C)，我们无法立即排除聪明的把戏(但我们确实让它们不太可能)。

话虽如此，您的问题可以转化为 A+B-C=0，在我看来，这样的解决方案将在不到 O(n²) 的时间内解决 3SUM > 还有……

---

考虑这个问题的解决方案:

考虑 2SUM 问题的解决方案(即找到 2 个总和为特定值的元素列表)。我们可以散列数组中的每个元素(或具有恒定时间查找的其他一些数据类型)。插入每个元素需要 O(n) 时间。这是 2SUM 问题的线性解。 (然后循环遍历数组中的每个元素并检查 T-element 的散列)

采用这种思路，我们可以对数组中的每个和进行哈希处理。但是，获得所有可能的组合最多需要 n*(n-1) 或 O(n²) 时间。

---

如果有人确实有比 O(n²) 更快的解决方案，我将永远对你的数字感到敬畏(如果我找到一个，我会编辑它并吃掉我的话)。

祝您搜索顺利!