给定一个数组，例如 [1, 0, -1, 2, 3, 4, 5] ，找到长度为3的所有子集，其中一个元素等于子集中其他两个元素的总和 . 例如：
[1, 0, -1, 2, 3, 4, 5]
1 + -1 == 0 (from [1, 0, -1]) 2 + 3 == 5 (from [2, 3, 5])
我提出了一个 O(n²) 解决方案，但我的采访者坚持认为有一个 O(n log n) 解决方案 .
O(n²)
O(n log n)
解决这个问题的最佳方法是什么？
乍一看，我看不到一个小于 O(n²) 的算法 . （除非它是一个非常聪明的人）
这个问题与臭名昭着的3SUM问题非常相似：基本上，这个想法是给定一组n个元素，是否有任何三元组总和为零？
比 O(n²) 更快地解决3SUM的算法尚不清楚 - 这是计算机科学中的一个开放性问题......（见这里：http://en.wikipedia.org/wiki/3SUM）
但是，由于你的问题不完全是3SUM（ A+B+C=0 ），而是涉及（ A+B=C ），我们不能立即排除聪明的技巧（但我们确实使它们不太可能） .
A+B+C=0
A+B=C
话虽这么说，你的问题可以转化为 A+B-C=0 ，在我看来，这样的解决方案也可以在不到 O(n²) 的情况下解决3SUM ......
A+B-C=0
考虑这个问题的解决方案：
考虑2SUM问题的解决方案（即，找到总和为某个值的2个元素列表） . 我们可以散列数组中的每个元素（或者使用常量时间查找的其他数据类型） . 插入每个元素需要 O(n) 次 . 这是2SUM问题的线性解决方案 . （然后循环遍历数组中的每个元素并检查哈希的 T-element ）
O(n)
T-element
考虑到这个想法，我们可以散列数组中的每个总和 . 但是，获得所有可能的组合充其量只需要 n*(n-1) 或 O(n²) 时间 .
n*(n-1)
如果有人确实有一个比_2525777更快的解决方案，我将永远敬畏你的数字（如果我找到一个，我会编辑它并吃掉我的话） .
祝你好运！
1 回答
乍一看，我看不到一个小于
O(n²)的算法 . （除非它是一个非常聪明的人）这个问题与臭名昭着的3SUM问题非常相似：基本上，这个想法是给定一组n个元素，是否有任何三元组总和为零？
比
O(n²)更快地解决3SUM的算法尚不清楚 - 这是计算机科学中的一个开放性问题......（见这里：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²)时间 .如果有人确实有一个比_2525777更快的解决方案，我将永远敬畏你的数字（如果我找到一个，我会编辑它并吃掉我的话） .
祝你好运！