algorithm - 我们可以在 O(n^2) 中做 4 和算法吗？

Question

这与以下问题有关:

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} ) 时间?

谢谢!

Answer 1

有一些微妙之处，但您是对的，决策问题的平均性能可以做得很好。然而，它需要两个 HashMap ，而不是一个。

第一个 HashMap 从左开始，它将存储为值 (i1, j1)其中 i1 < j1和 j1是可以达到该总和的最小指标。

第二个 HashMap 从右边开始，它将存储为值 (i2, j2)其中 i2 < j2和 i2是可以达到该总和的最大索引。

现在遍历第一个 hashmap 的键，在另一个中寻找相反的键。如果两者都在那里并且j1 < i2然后你有你的四倍。

但是请注意一个微妙之处。通过排序，预期和最坏情况下的时间是 O(n^2 log(n)) .使用哈希，您的预期时间是 O(n^2)但理论上可以得到 O(n^4)如果您的哈希算法出现故障。 (哈希算法在实践中通常不会失效，这就是我们将它们视为 O(1) 的原因。)