在三个数组列表中查找总和为零的记录组合？

Question

考虑有三个相同长度的数组列表,其中包含正数,负数和零.我不得不写一个程序来找到总和为零的组合.所以基本上,如果阵列是: -

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

O/P:A [0] + B [0] + C [0],A [2] + B [2] + C [2]等.

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

还有其他方法吗？

谢谢.

编辑: 基于下面给出的答案,我的第一次解决是最快的.但是,如果问题是关于"发现"组合的数量和不打印它们,然后请参阅下面格里戈尔Gevorgyan回答.

Answer 1

可以用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的排序不是必需的，只是为了看起来不错:)