algorithm - 找到具有给定总和的三元组

Question

一段时间以来，我一直在为这个问题而苦苦挣扎。问题是这样的:-

我们有 n^2 个数字。我们需要找出是否存在满足 a+b+c = 0 的三元组 a,b,c。对于更一般的情况，a+b+c = k。 (给定k)

存在复杂度为 O(n^2log(n)) 的解。

如有任何帮助，我们将不胜感激。

谢谢

Answer 1

要在 O(n²logn) 中得到这个，您必须对数字进行排序。找到 2 个数字的所有组合，然后进行二分查找找到第三个。

问题的一般版本的上限要高得多。