3

我正在为我的校园实习做准备。我遇到了一个问题，它是这样的：

给定 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

4 回答 4

7

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

给定一个目标 T

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

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

对于第三个数组，您还可以使用哈希表，从而为您提供O(1)每次查找的预期复杂度，因此O(n^2)总体而言，但我总是觉得这有点作弊，因为您依赖于分布良好的集合。

于 2013-09-30T12:57:25.750 回答
6

该问题与3SUM 问题密切相关。事实上，3SUM 问题可以简化为您所说的问题（三个数组填充相同的 n 个元素），所以问题是3SUM-hard。

因此，比 O(n^2) 更快的解决方案极不可能，因为这与 3SUM 问题的推测二次时间下限相矛盾。

于 2013-09-30T13:16:20.783 回答
2

你可以在 O(n^2) 中做到这一点：

  • 将第二个数组按升序排序
  • 对第三个数组进行降序排序
  • 循环遍历第一个数组。

  • 根据总和是负数还是正数，增加第二个或第三个数组的索引。

    // Asssume array2 and array3 are sorted as mentioned above
// array2: {-8,-3,0,3}
// array3: {6,-1,-4,-7}
foreach (e1 in array1)
{
    int i2 = 0;
    int i3 = 0;
    while (i2 < array2.Length && i3 < array3.Length)
    {
        int sum = e1 + array2[i2] + array3[i3];
        if (sum == 0) Console.WriteLine( e1, array2[i2], array3[i3]);
        if (sum < 0) ++i2 else ++i3;
    }

    }

相关：在数组中查找三个元素之和最接近给定数字

于 2013-09-30T13:02:55.687 回答
1

O(log(N) * N^2)如果您对一个数组进行排序并执行二进制搜索以否定其他两个数组中任何一对元素的总和，则可以降低复杂性。

如果数组中数字的值范围相对较小，您可以通过使用计数排序算法或其他一些线性非比较排序算法来进一步改善这一点。

另一个改进是对第一个数组的数字使用哈希集，从而得到 Kevin 提出的 O(N^2) 的复杂度。

于 2013-09-30T12:58:40.947 回答