9

それぞれ長さが同じで、正、負、ゼロを含む 3 つの配列リストがあるとします。合計がゼロになる組み合わせを見つけるプログラムを書かなければなりませんでした。したがって、基本的に、配列が次の場合:-

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 ループを作成し、a[i] + b[j] + c[k] を使用して合計を計算します。ゼロの場合はインデックスを出力します。Big O は O(N^3) になります。 2. for ループが 2 つありますが、バイナリ検索を使用して、合計がゼロになる 3 番目の要素を見つけます。Big O は O(N^2LogN) になります

他の方法はありますか？

ありがとう。

編集: 以下の回答に基づいて、私の最初のソルンは可能な限り最速です。しかし、質問が組み合わせの数を「見つける」ことであり、それらを印刷しないことである場合は、以下のGrigor Gevorgyanの回答を参照してください。

4

4 に答える 4

3

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.

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 :)

于 2012-07-20T10:09:42.840 に答える
2

私はこの3SUMだと思います：

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

ウィキペディアの記事を引用するには：

O(n2) 時間で 3SUM を解決する単純なアルゴリズムがあります。最初に配列内の各要素をハッシュし、考えられるすべてのペアを見つけ、最後に残りの値の存在をチェックします (これは単純に各ペアの合計のマイナスです)。ハッシュテーブルを使用。

于 2012-07-22T04:11:39.933 に答える
1

このソリューションは、与えられたデータをファイルや入力ストリームなどのストレージから自分で配列リストに読み込んでいる場合にのみ高速化されます。3番目の配列リストをに置き換えるとhashtable、ゼロサムの3番目のコンポーネントを検索するための一定の時間が得られます。2つのネストされたループでは、新しいペアを取得するたびa[i]+b[j]に、ハッシュテーブルで検索c[n0]=-a[i]+b[j]しますO(1)。したがって、合計時間計算量はO（n ^ 2）です。このソリューションは、読み取りプロセスの習得が許可されている場合にのみ役立ち、配列リストが既に提供されている場合は何も高速化されないことを明確にしておきます。

于 2012-07-22T18:56:29.370 に答える
1

単純なアプローチはすべてのサブセットをチェックすることですが、これは実行時間が非常に短くなります。 http://mathworld.wolfram.com/k-Subset.html これ以上の制限はありませんが、これは NP 完全部分集合和の問題だと思います。まともな解決策を提供するナップザック問題に関連する解決策があります。 http://en.wikipedia.org/wiki/Subset_sum_problem

合計が 0 になるすべての組み合わせを見つける必要がありますか?それとも 1 つだけですか?それとも 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 に答える