9

考虑有三个数组列表，每个列表长度相等，并且其中有正数、负数和零。我必须编写一个程序来查找总和为零的组合。所以基本上，如果数组是： -

A = {0, -1, 2}
B = {0, -1, -2}
C = {0, -2, 0}

输出/输出：A[0] + B[0] + C[0]、A[2] + B[2] + C[2] 等。

我可以想到两种方法，1. 有 3 个 for 循环并使用 a[i] + b[j] + c[k] 计算总和，如果为零则打印索引。大 O 将是 O(N^3) 2. 有两个 for 循环，但使用二分搜索找到第三个元素，它将使总和为零。大 O 将是 O(N^2LogN)

还有其他方法吗？

谢谢。

编辑： 根据下面给出的答案，我的第一个解决方案是最快的。但是，如果问题是关于“查找”组合的数量而不是打印它们，那么请参阅下面的 Grigor Gevorgyan 回答。

4

4 回答 4

3

可以用2 指针方法在O(n^2)中完成。 对数组进行排序。现在执行以下操作： 设置ans = 0。 有一个外部循环通过索引为i的数组a运行。现在设置j = 0, k = n - 1。 看看sum = a[ i ] + b[ j ] + c[ k ]。 如果sum < 0，则增加j。 如果sum > 0减少k。 如果sum == 0，找到等于b[ j ]和c[ k ]的元素范围，并将范围长度乘积添加到答案中。然后设置







j和k到该范围之外的第一个元素。
这是有效的，因为数组是排序的并且加法是一个线性函数。
内部部分以O(n)运行，总体复杂度为O(n^2) 。

C++ 中的示例代码：

sort( a, a + n );
sort( b, b + n );
sort( c, c + n );
ans = 0;
for( i = 0; i < n; ++i )
{
   j = 0, k = n - 1;
   while( j < n && k > 0 )
   {
      sum = a[ i ] + b[ j ] + c[ k ];
      if( sum < 0 ) ++j;
          else if( sum > 0 ) --k;
          else 
          { 
             // find the equal range
             for( jj = j; jj < n && b[ jj ] == b[ j ]; ++jj );
             for( kk = k; kk >= 0 && c[ kk ] == c[ k ]; --kk );
             // add pairs quantity from these ranges
             ans += ( jj - j ) * ( k - kk );
             j = jj, k = kk;
          }
}

注意：数组a的排序不是必需的，只是为了看起来不错:)

于 2012-07-20T10:09:42.840 回答
2

我认为这个 3SUM：

http://en.wikipedia.org/wiki/3SUM

引用维基百科的文章：

有一个简单的算法可以在 O(n2) 时间内解决 3SUM，方法是首先对数组中的每个元素进行散列，找到所有可能的对，然后最后检查剩余值是否存在（这只是每对总和的负数）使用哈希表。

于 2012-07-22T04:11:39.933 回答
1

天真的方法是检查所有子集，但这运行时间很差。 http://mathworld.wolfram.com/k-Subset.html 没有进一步的限制，我相信这是NP完全子集和问题。有一个与背包问题相关的解决方案，它给出了一个不错的解决方案。 http://en.wikipedia.org/wiki/Subset_sum_problem

您是否需要找到总和为 0 的所有组合，或者只是一个组合，或者只是一个具有 3 个元素的解决方案？

解决方案应该是 {{A[0]},{B[0]}, {C[0]}, {C[2]}, {A[0],B[0]},{A[0], B[0],C[0]},{A[0],B[0],C[0],C[2]},{A[1],B[1],A[2]}, {A[2],B[2]} 等等}

于 2012-07-20T08:59:09.217 回答
1

仅当您将给定的数据从某些存储（例如文件或任何输入流）中读取到数组列表中时，此解决方案才会加快速度。将第三个数组列表替换hashtable为为您提供了一个恒定的时间来查找零和的第三个组成部分。在您的两个嵌套循环中，每次获取新对时a[i]+b[j]，您都在哈希表中查找c[n0]=-a[i]+b[j]需要的内容O(1)。所以总的时间复杂度是O(n^2)。让我澄清一下，这个解决方案只有在您被允许掌握阅读过程时才有帮助，并且如果您已经获得了数组列表，则不会加速任何事情。

于 2012-07-22T18:56:29.370 回答