キャンパスプレースメントの準備をしています。次のような質問に出くわしました。
次のような 3 つの配列が与えられた場合
array 1: {2,1,4,7}
array 2: {3,-3,-8,0}
array 3: {-1,-4,-7,6}
各配列から 1 つの数値を抽出し、トリプレット内の数値の合計が 0 になるようにトリプレットを形成する必要があります。
たとえば、上記の場合、解決策の 1 つは次のようになります。{2, -8, 6}
現在のところ、時間のかかる総当り法以外に解決策が思い浮かびませんO(n^3)。より短い時間でこれを行う方法は？
前もって感謝します。
この問題は3SUM 問題と強く関連しています。実際、3SUMの問題は、あなたが述べた問題（同じn要素で満たされた3つの配列）に還元できるため、問題は3SUM-hardです。
したがって、O(n^2) よりも高速な解はほとんどありません。これは、3SUM 問題の予想される 2 次時間の下限と矛盾するためです。
O(log(N) * N^2)1 つの配列を並べ替えて、他の 2 つの配列の要素のペアの合計を否定するバイナリ検索を実行すると、複雑さを軽減できます。
配列内の数値の値の範囲が比較的小さい場合は、カウントソートアルゴリズムまたはその他の線形非比較ソートアルゴリズムを使用して、これをさらに改善できます。
もう 1 つの改善点は、最初の配列の数値にハッシュセットを使用することです。これにより、Kevin によって提案された O(N^2) の複雑さが得られます。