从每个数组中提取一个数字,使数字之和为0？

Question

我正在为我的校园安置做准备.我遇到了一个问题,如下所示:

给出3个阵列,比如

array 1: {2,1,4,7}
array 2: {3,-3,-8,0}
array 3: {-1,-4,-7,6}

我们必须从每个数组中提取一个数字并形成三元组,使得三元组中的数字之和为0,或者为该事实的任何数字.

例如,对于上述情况,其中一个解决方案可以是 {2, -8, 6}

目前,我还没有想到除了暴力方法之外的任何解决方案,这需要O(n^3)时间.如何在较短的时间内完成这项工作？

提前致谢.

Answer 1

一个非常简单的解决方案如下:

给定目标T

• 排序第三个数组
• 对于第一个数组中的每个数字N1
  • 对于第二个数组中的每个数字N2
    • 二进制搜索第三个数组(T - N1 - N2)

运行时间= O(n^2 log n)

对于第三个数组,你也可以使用一个哈希表,给你一个预期的O(1)每次查找的复杂性,因此O(n^2)总的来说,但我总觉得这有点作弊,因为你依赖于集合的良好分布.

Answer 2

这个问题与3SUM问题密切相关.实际上,3SUM问题可以简化为你所说的问题(三个数组填充相同的n个元素),所以问题是3SUM-hard.

因此,比O(n ^ 2)解更快的解决方案是不太可能的,因为这将与3SUM问题的猜想二次时间下限相矛盾.