[解決済み] 配列中の3つの要素のうち、和が与えられた数値に最も近いものを探す

質問

整数の配列 A が与えられたとき <サブ 1 , A <サブ 2 , ..., A <サブ n ここで，配列の中から，その和が与えられた整数Sに最も近い3つの異なる整数を見つける必要があります．

すべての整数はint32_tの範囲にあり、和を計算しても算術オーバーフローは発生しないと考えてよい。S は特別なものではなく、ランダムに選ばれた数である。

3つの整数を見つけるのに、ブルートフォースサーチ以外に効率的なアルゴリズムはありますか？

どのように解決するのですか？

ブルートフォースサーチ以外に、3つの整数を見つける効率的なアルゴリズムはありますか？

そう、これをO(n)で解くことができる。 ² )時間です! まず、あなたの問題を考えてみましょう P は、少し違う方法で同等に言い表すことができ、"ターゲット値"は不要になります。

元の問題 P : ある配列が与えられると A の n 整数値と目標値 S からの3タプルは存在するか？ A という和になります。 S ?

修正問題 P' : ある配列が与えられると A の n の3タプルは存在するか？ A の和が0になるようなものですか？

この問題のバージョンから行くことができることに注意してください。 P' から P の各要素から自分のS/3を減算することにより A しかし、これで目標値は不要になりました。

単純に可能な3タプルをすべてテストすれば、O(n)で解決することは明らかです。 ³ ) -- これがブルートフォース・ベースラインです。もっといい方法はないだろうか？もっとスマートな方法でタプルを選んだらどうでしょう？

まず、配列のソートに時間をかけますが、これには初期費用としてO(n log n)のペナルティがかかります。次に、このアルゴリズムを実行します。

for (i in 1..n-2) {
  j = i+1  // Start right after i.
  k = n    // Start at the end of the array.

  while (k >= j) {
    // We got a match! All done.
    if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])

    // We didn't match. Let's try to get a little closer:
    //   If the sum was too big, decrement k.
    //   If the sum was too small, increment j.
    (A[i] + A[j] + A[k] > 0) ? k-- : j++
  }
  // When the while-loop finishes, j and k have passed each other and there's
  // no more useful combinations that we can try with this i.
}

このアルゴリズムは、3つのポインタを配置することで動作します。 i , j および k を配列のさまざまな位置に配置します。 i は先頭から始まり、ゆっくりと最後へ向かっていきます。 k は一番最後の要素を指します。 j はどこを指すかというと i で始まっています。それぞれのインデックスにある要素を繰り返し合計しようとすると、そのたびに次のようなことが起こります。

• 和がぴったり! 答えが見つかったのです。
• 合計が小さすぎました。移動 j を最後に近づけて、次に大きな数字を選択します。
• 合計が大きすぎました。移動 k を先頭に近づけて、次に小さい数字を選択します。

それぞれについて i のポインタは j と k は、徐々にお互いに近づいていきます。最終的にはすれ違うので、その時はもう何も試行する必要はありません i というのも、順番が違うだけで、同じ要素の和をとっているからです。この後、次の i を繰り返す。

最終的には、有用な可能性を使い切るか、解決策を見出すことになる。これは、O(n ² というのは、外側のループをO(n)回実行し、内側のループをO(n)回実行するからです。整数をビットベクトルで表現し、高速フーリエ変換を行うことで、これを準定常的に行うことも可能ですが、それはこの解答の範囲外です。

注 このアルゴリズムでは、同じ要素を複数回選択することができます。つまり、(-1, -1, 2)も(0, 0, 0)と同じように有効な解答となるのです。また、このアルゴリズムでは 正確 の答えは、タイトルにあるように、最も近い答えではなく、答えです。読者への練習として、distinct elements only (but it's a very simple change) and exact answers (which is also a simple change)で動作するようにする方法を考えてもらうことにします。