a + b + c = zとなるようにa、b、cが配列内に存在するかどうかを決定するアルゴリズム。

Question

次の問題のための効率的なアルゴリズムを見つけるのに少しでも立ち往生しました。 algoは、a + b + cが与えられた数zに等しくなるように、配列中に3つの要素a、b、cがあるかどうかを決定しなければならない。

もちろん、組み合わせを試してみるのが賢明ですが、漸近的に必要な時間は大きすぎます。

合計がzになるように配列のaとbを見つける方がはるかに簡単です。指定された配列を昇順にソートし、z-aが存在する場合はすべての要素をチェックします。しかし、3要素の問題でどのように実装するのか、何時必要なのかは分かりません。

ご協力いただきありがとうございます。

編集：a、b、c、zは整数です。

Answer 1

このアプローチは、合計zを持つaおよびbを見つけることと非常によく似ています。

最初に配列を並べ替えます。そして、位置iで固定し、合計zがaとbに存在するかどうかをチェックするO(n)アルゴリズムを持っているので、あなたが制限i + 1 to n

で合計z-aを持っているかどうかを確認します。私たちは、修正し、他の二つの変数が合計を生成するために使用することができるかどうかを確認するためにそれを拡張します。 here

// returns true if there is triplet with sum equal 
// to 'sum' present in A[]. Also, prints the triplet 
bool find3Numbers(int A[], int arr_size, int sum) 
{ 
    int l, r; 

    /* Sort the elements */ 
    sort(A, A+arr_size); 

    /* Now fix the first element one by one and find the 
     other two elements */ 
    for (int i=0; i<arr_size-2; i++) 
    { 

     // To find the other two elements, start two index 
     // variables from two corners of the array and move 
     // them toward each other 
     l = i + 1; // index of the first element in the 
        // remaining elements 
     r = arr_size-1; // index of the last element 
     while (l < r) 
     { 
      if(A[i] + A[l] + A[r] == sum) 
      { 
       printf("Triplet is %d, %d, %d", A[i], 
             A[l], A[r]); 
       return true; 
      } 
      else if (A[i] + A[l] + A[r] < sum) 
       l++; 
      else // A[i] + A[l] + A[r] > sum 
       r--; 
     } 
    } 

    // If we reach here, then no triplet was found 
    return false; 
} 

Answer 2

私は答えとして短いコメントを書いていたはずですが、私はそれに十分な評判を持っていないと思います。

---

私は今を考え出すことができる最高のアルゴリズムは、より良い私たちはA + B = Z Oで（n）の場合（またはO（で始まるものとし、このアルゴリズムを説明するために、（N^2）Oでありますnlgn）それがソートされなかった場合）全ての

まず、{A}反復、及び{B}よう+ B = Zを見つけます。あなたがすべてのbを反復するならnaively、これは{（a）}あたりO（n）を要し、O（n^2）の解につながります。しかし、{a}を繰り返し反復する場合、{b}の値は厳密に減少しなければなりません。我々は、このコードのように時間の複雑さを軽減するために、この情報を利用することができる。

for a = first element, b = last element; a != last; a = next a 
while ((b != first element) and (a + b > z)) 
     b = previous elemnet of b 
if a + b == z 
     return true 

注{B}は一度だけループを通してリスト全体を通過し、それは償却O（N）の複雑さを持っていること。

今は元の問題にこの原理を適用することができ、我々は{A}を反復し、このO（N）アルゴリズムを適用することができる

---

{B、C} {ZA}を見つけるために、合計複雑O（n * n = n^2）です。

がうまくいけば、より低い複雑で解決策があると、私はO（N^2）が印象的であるとは思わないが、私はちょうど良く1を思い付くことができません。