algorithm - 以下の例のように、すべての可能性を出力します。

Question

ソートされた配列を指定すると、ab=c となるすべてのトリプレットを出力します。配列の例は {-24, -15, -8, -6, 0, 3, 6, 9, 17, 36} です。

Answer 1

O(n^2)次のプロパティに基づいて解決策を提案します。修正aして順次増加するとb、c減少します。したがって、次のようにできます。

    for( i = 0; i < arr.size(); i++ ) // index of a
    {
        t = arr.size() - 1; // index of possible c
        for( j = 0; j < arr.size(); j++ ) // index of b
        {
            a = arr[ i ];
            b = arr[ j ];
            c = a - b;
            while( t >= 0 && arr[ t ] > c ) // using monotonicity
               t--;
            if( t >= 0 && arr[ t ] == c )
            { /* output a, b, c */ }
        }
    }

Answer 2

O(n^2)すべてa - bをハッシュ テーブルに格納してから、配列内の各要素のハッシュをクエリすることで実行できますc。

Answer 3

Haskell バージョン:

triples set = 
  [[a,b,c] | a <- set, b <- set, b /= a, c <- set, c /= b && c /= a, a - b == c]

*Main> トリプル [-24, -15, -8, -6, 0, 3, 6, 9, 17, 36]
[[-15,-24,9],[-15,9,-24], [-6,-15,9],[-6,9,-15],[0,-6,6],[0,6,-6],[3,-6,9],[3, 9,-6],[9,-8,17],[9,3,6],[9,6,3],[9,17,-8]]