查找记录的所有组合这些款项零三个数组列表？ [英] Find all combinations of records which sums to zero in three array lists?

问题描述

考虑有各相等的长度，并具有正，负，在其中零3数组列表。我不得不写一个程序，找出其中的组合的总和变为零。所以基本上，如果数组是： -

Consider there are three array list each of equal length and having positive, negative and zero in them. I had to write a program to find combinations of which sum comes to zero. So basically, if the arrays were:-

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]等

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

我能想到的两种方式， 1.有3回路，并使用[I] + B [J] + C [K]计算总和，如果零打印索引。    大O将是O（N ^ 3） 2.有两个用于循环，但用二进制搜索查找，这将使之和为零的第三个元素。    大O将是O（N ^ 2LogN）

I could think of two ways, 1. Have 3 for loops and calculate the sum using a[i] + b[j] + c[k], if zero print the index. Big O will be O(N^3) 2. Have two for loop but use Binary Search to find the third element which would give the sum as zero. Big O will be O(N^2LogN)

其他方法吗？

感谢。

编辑： 根据下面给出的答案，我的第一个SOLN是最快的。但是，如果问题是关于寻找的组合数和不可以打印它们，那么请参阅格里戈尔Gevorgyan回答以下。

Based on the answers given below, my first soln is the fastest possible. But if the question is about "finding" the number of combinations and NOT printing them, then please see Grigor Gevorgyan answer below.

推荐答案

可以在 为O（n ^ 2）的与 2的指针方法。

排序的数组。现在做如下：
将的 ANS = 0 的。
必须通过阵列上运行的外部环路的的在的与指数的的我的。现在，将的 J = 0，K = N - 1 的
看的的和= A [1] + B [J] + C [K] 的。
 如果 总和＆LT; 0 的，增加的的Ĵ的。
 如果 总和> 0 的减少的的 K 的。
 如果 总和== 0 的，发现元素等于范围的的乙[J] 的和 C [K] 的并添加范围长度的产品给答案。然后，将的Ĵ的和的 K 的以第一要素出来的，范围。
 这样做是因为数组的排序和相加是线性函数。
内部部分运行的 O（N），与整体的为O（n ^ 2）的复杂性。

Can be done in O(n^2) with 2 pointers method.

Sort the arrays. Now do following:
Set ans = 0.
Have an external loop running through array a with index i. Now set j = 0, k = n - 1.
Look at sum = a[ i ] + b[ j ] + c[ k ].
If sum < 0, increase j.
If sum > 0 decrease k.
If sum == 0, find the range of elements equal to b[ j ] and c[ k ] and add ranges lengths product to the answer. Then set j and k to first elements out of that ranges.
This works because arrays are sorted and addition is a linear function.
Internal part runs in O(n), with overall O(n^2) complexity.

例如code C ++中：

Example code in 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;
          }
}

注意的：排序数组的的在的是没有必要的，只是这样做是为了好看：）

Note: Sorting of array a is not necessary, just did it to look good :)

这篇关于查找记录的所有组合这些款项零三个数组列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！