整数の集合が与えられた場合、問題は長さ 3 の可能な算術級数の数を見つけることからなります。整数の集合はソートされている場合とソートされていない場合があります。
O(n^3) 時間かかる単純なブルートフォース アルゴリズムを実装できますが、時間効率が重要であり、整数のセットは 10^5 まで大きくなる可能性があります。これは、ブルートフォースが明らかに機能しないことを意味します。誰かがC ++でアルゴリズム/疑似コード/コードを提案できますか?
例: 4 つの数字 5,2,7,8 があります。公差が 3 である (2,5,8) の可能性は 1 つしかないので、答えは 1 です。
編集: 1 つの重要なプロパティについて言及するのを忘れていました。指定されたセットの各数は 1 から 30000 (包括的) です。
次のように O(N^2) で実行できます: 内の要素の有無を確認できるように、整数のハッシュ セットを作成しますO(1)。その後、セット要素のすべてのペアに対して 2 つのネストされたループを作成します{X, Y}。これは で行われO(N^2)ます。
各ペア について{X, Y}、 と仮定しX < Y、2 つの数値を計算します。
Z1 = X - (Y-X)
Z2 = Y + (Y-X)
次の場合、トリプル{X, Y, Zi}は算術シーケンスを形成しますZi != X && Zi != Y && set.contains(Zi)
トリプル{X, Y, Z1}との両方をチェックし{X, Y, Z2}ます。O(1)のアルゴリズムの合計実行時間に対して、ハッシュ セットを使用してそれを行うことができますO(N^2)。
O(N+BlogB) (B は整数の最大サイズ - あなたの場合は 30,000) である代替ソリューションは、ヒストグラム H を考慮することです。ここで、H[x] は x がシーケンスに存在する回数です。 .
このヒストグラムは、時間 N で計算できます。
ba=cb となる要素 a、b、c を探しています。これは 2b=a+c に相当します。
したがって、a+c の 2 番目のヒストグラム G[x] を計算し、すべての要素 b をループして、合計に H[b]*G[2b] を追加するという考え方です。これには時間 O(B) がかかります。
(G[x] は、x=a+b となる値 a、b のペアがシーケンス内に存在する回数です。)
唯一の問題は G[x] の計算ですが、これは高速フーリエ変換を使用して H[x] を時間 O(BlogB) で畳み込むことで実行できます。