algorithm - 在 3 个数组中的每一个中找到 3 个总和为给定值的元素

Question

令 A 、 B 、 C 为 3 个数组，每个数组包含 n 个元素。求一个算法判断A中是否存在a，B中是否存在b，C中是否存在c使得a+b+ c = k.

我尝试了以下算法，但它需要 O(n²):

1. 对所有 3 个数组进行排序。 - O(n log n)

2. 临时数组h = k - (a+b) - O(n)

3. 对于每个 h，在 B 中找到 c' 使得 c' = h - B[i] - O(n)

4. 使用二进制搜索在 C 中搜索 c' - O(log n)

总计 = O(n log n) + O(n) + O(n² log n)

我们可以在 O(n log n) 中解决吗？

Answer 1

您的问题询问如何在线性算数时间内解决问题 3SUMx1，该问题在随机线性时间内显示为减少到 3SUMx3。参见 here减少。

除非你要发表一些非常大的东西，否则我怀疑你的问题会有这么快的算法，它至少和 3SUM 一样难(你也可以通过一些工作来显示相反方向的减少，也是)。

编辑:为了使上面的段落清楚，线性时间减少从3SUM证明OP的问题是$\Omega(n^{1.5})$。