algorithm - -1 と 1 の間の x+yz

Question

範囲内の個別の整数[a_1 a_2 ... a_n]のリストとします。のように異なる要素が 3 つある場合に返す、そうでない場合に返すアルゴリズムを与えてください。[1,10n]truex,y,z-1 <= x+y-z <= 1false

ブルート フォース アルゴリズム ( のすべての可能な組み合わせをチェックしx+y-z、時間内に実行されO(n^3)ます。より効率的なアルゴリズムはありますか?

Answer 1

はいあります。これは、追加のスペースO(n^2)を使用する最悪のケースのアルゴリズムです。O(n)

アイデアは、(トリプルの代わりに) 可能なすべてのペアをチェックし、既に見た要素を繰り返しマークし、それらと各ペアの合計を比較することです。
各ペアについて、その合計が一致する要素を持っていることを確認します。これは、正確に合計 ( x+y-z == 0) または 1 を追加した場合に取得できる要素 ( ) または 1x+y+1-z == 0 -> x+y-z = -1を削減した場合に取得できる要素 ( x+y-1-z == 0 -> x + y - z == 1)です。

擬似コード:

mark = new boolean[10n]; //all initialized to false
sort arr //O(nlogn)
for each i in n,1: (reverse order)
   for each j in 1,i-1:
      //neglected range check, make sure it is done
      if (mark[arr[i]+arr[j]] || mark[arr[i]+arr[j]+1] || mark[arr[i]+arr[j]-1]):
          return true
      mark[arr[i]] = true
return false

iから1 まで反復することに注意してくださいn。なぜならz > x、そしてz > y- そして、リストに既に存在する要素とのすべてのペアをチェックしていることを確認したいからです。

正しさの証明:
解がある場合x+y-z = 0-z > xそしてz > y(すべての要素は正の異なる整数です)。
一般性を失うことなく、 と仮定しましょうx > y。arr[i]=xしたがって、外側のループで反復する場合、j<iそのようなものがありarr[j]=yます。また、以前に反復したときにマークしたためです z>x。したがって: アルゴリズムは を見つけ、 を生成します。 ケースの同様の証拠。mark[z] == true
mark[arr[x] + arr[y]] == truetrue
+-1

アルゴリズムが true を返した場合、条件の 1 つが true であることがわかりました。そうだとしましょうmark[arr[i] + arr[j]](他の場合の証明も同様です)。 というような要素があり、アルゴリズムはこの場合には正しいので、それを挿入し
ました。mark[arr[i] + arr[j]] == truezz = arr[i] + arr[j]