我们能在O(n^2)的时间复杂度内实现4-sum算法吗？

Question

这与以下问题有关：https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem 不失一般性，让我们只考虑偶数的k，或者只考虑k = 4。

我的问题是，在对所有数字对求和后，是否有必要对和的列表进行排序？我知道我们可以使用从左和右两个指针来夹住两对数字，时间复杂度为O(n^2)，但排序需要O(n^2 log(n))的时间。

如果我们使用哈希表将和作为键，它们对应的索引对作为值存储，那么所有操作都可以在O(n^2)的时间内运行。

我在那篇文章中漏掉了什么，或者说对于偶数的k，k-sum 可以在O(n^{k/2})的时间内运行吗？

谢谢！

- Kaa1el

---

你想要计算四个数的和的数量还是打印出这四个数？ - Kaidul

@Kaidul 我认为这两个应用程序的复杂度都是相同的。但是假设我们想要打印出所有这样的4元组。 - Kaa1el

不，如果你想列出所有的四元组，复杂度会高得多。 - Kaidul

@Kaidul 在哈希映射中，我们可以存储所有索引对的列表，这些索引对的和为该数字。然后我们只需要从两个这样的索引对枚举四元组即可打印出它们。这不应该增加复杂度。 - Kaa1el

@Kaidul，也许我错了，但让我们回到说我们只需要打印一个这样的四元组或者只是检查列表是否有这样的四元组的决策问题。即使在这种情况下，我也不能确定为什么我们需要对总和进行排序。 - Kaa1el

Answer 1

有一些微妙之处，但你说的对，决策问题的平均性能可以做得很好。然而，这需要两个哈希映射表，而不是一个。

第一个哈希映射表是从左边开始的，并将(i1, j1)存储为值，其中i1，j1是可以实现该总和的最小索引。

第二个哈希映射表是从右边开始的，并将(i2, j2)存储为值，其中i2，i2是可以实现该总和的最大索引。

现在遍历第一个哈希映射表的键，查找另一个哈希映射表中的相反内容。如果两者都存在且j1，那么你就有了四元组。

然而请注意微妙之处。通过排序，期望和最坏情况的时间复杂度为O(n^2 log(n))。使用哈希，期望时间复杂度为O(n^2)，但如果哈希算法失效，则理论上可能会达到O(n^4)。（哈希算法通常不会在实践中失效，因此我们认为它们是O(1)。）

- btilly