我们可以在O(n^2)中做4-sum算法吗？
这与以下问题有关：
https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem
在不失去一般性的情况下，让我们只考虑k，或者只考虑k = 4。
我的问题是，在对所有数字对求和之后，是否有必要对和列表进行排序？我知道我们可以使用左右两个指针在O(n^2)时间内夹住这两个指针对，但是排序需要O(n^2 log(n))时间。
如果我们使用hashmap将和存储为键，并将其相应的索引对存储为值，那么所有操作都可以在O(n^2)时间内运行。
我是不是在那篇文章中遗漏了什么，或者即使是k，k-sum也可以在O(n^{k/2})时间运行？
谢谢!
回答 1
Stack Overflow用户
发布于 2018-09-13 05:31:41
有一些微妙之处，但您是对的，决策问题的平均性能可以做到如此之好。但是，它需要两个hashmap，而不是一个。
第一个哈希图是从左边开始的，它将存储为值(i1, j1)，其中i1 < j1和j1是可以达到该和的最小索引。
第二个哈希图从右边开始，它将存储为值(i2, j2)，其中i2 < j2和i2是可以达到该和的最大索引。
现在遍历第一个hashmap的键，在另一个中寻找相反的键。如果两个都在那里，并且是j1 < i2，那么你就有了你的四元组。
然而，请注意其中的微妙之处。通过排序，期望和最坏情况的时间是O(n^2 log(n))。使用散列，你的预期时间是O(n^2)，但是如果你的散列算法崩溃了，理论上是可以得到O(n^4)的。(散列算法在实践中通常不会中断，这就是我们将其称为O(1)的原因。)
https://stackoverflow.com/questions/52302895
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号