从每个数组中提取一个数字，以便数字之和为0？
从每个数组中提取一个数字，以便数字之和为0？
提问于 2013-09-30 12:51:30
我正在为我的校园安置做准备。我遇到了一个问题，是这样的：
给定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)时间。如何在较短的时间内做到这一点？
提前谢谢。
回答 4
Stack Overflow用户
回答已采纳
发布于 2013-09-30 13:02:55
您可以在O(n^2)中这样做：
- 将第二个数组按升序排序
- 将第三个数组按降序排序
- 循环遍历第一个数组。
- 第二或第三阵列的增量指数取决于和是负还是正。 // array2和array3按上述// array2排序：{-8，-3,0,3} / array3：{6，-1，-4，-7} foreach (e1 in array1) { int i2 = 0；int i3 = 0；而(i2 < array2.Length & i3 }
Stack Overflow用户
发布于 2013-09-30 12:57:25
一个非常简单的解决方案如下：
给定目标T
- 排序第三个数组
- 对于第一个数组中的每个数字N1，
- 对于第二个数组中的每个数字N2，
- 二进制搜索第三个数组(T - N1 - N2)
- 对于第二个数组中的每个数字N2，
运行时间= O(n^2 log n)
对于第三个数组，您也可以使用哈希表，给出每次查找的O(1)的预期复杂性，因此总体上是O(n^2)，但我总是觉得这有点欺骗，因为您依赖于该集合是否分布良好。
Stack Overflow用户
发布于 2013-09-30 13:16:20
这个问题与3和问题密切相关。实际上，3 3SUM问题可以归结为您已经说明的问题(三个数组填充了相同的n个元素)，所以问题是3和硬。
因此，比O(n^2)更快的解是极不可能的，因为这与3和问题的猜想二次时间下界相矛盾。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19094770
复制相关文章
相似问题
腾讯云开发者
