问6SUM:给定一个由n个整数组成的集合S，是否存在S的一个子集，其中恰好有6个元素之和为0？如何做得比O(n^3)更好？
EN

Stack Overflow用户

提问于 2011-03-18 21:12:15

回答 1查看 368关注 0票数 3

我想了一个简单的算法来解决6SUM问题，它使用O(n^3)时间和空间:生成所有三元组的集合，并将它们放在一个哈希表中，其中关键字是三元组的总和。然后迭代哈希表的键:对于每个键k1，查看是否存在另一个键k2，使得k2 = S-k1

什么是更有效的算法？这不是一个家庭作业问题。

回答已采纳

发布于 2011-03-18 23:29:56

你的算法在最坏的情况下是Omega(n^6)，在平均情况下只有O(n^3)。您忽略了哈希表冲突的可能性。不过，您可以通过使用平衡树将其设置为O(n^3logn)。

此外，这是在P中，因为有一个简单的多项式时间算法来检查6个数字的每一个可能的组合，所以背包等的提及是无关的。

和3-SUM问题一样，我相信r-sum问题的算法是o(n^r/2)，(注意: smallOH >= x=最大整数x，例如5/2 = 3)。

在3-SUM页面的here中有一个简短的提到，其中有一个声明，上面的界限已经在有限的计算模型中得到了证明。

因此，比O(n^3) (即o(n^3))更好可能是一个悬而未决的问题。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/5352444

复制

相似问题

问6SUM:给定一个由n个整数组成的集合S，是否存在S的一个子集，其中恰好有6个元素之和为0？如何做得比O(n^3)更好？EN