配列内に存在するすべての要素を含む配列の中で最も短い範囲を見つける

Question

配列A []には別個の整数を入れることができますが、配列に含まれるすべての要素をカバーする最短範囲を見つけるにはどうすればよいですか？範囲[3,7]に

A[] = 7 3 1 7 3 1 3 4 1 
index= 0 1 2 3 4 5 6 7 8 

要素は、アレイ中に存在する最短距離を形成します。
したがって、答えは5でなければなりません。
ダブルポインタを使用してこの問題を解決するにはどうすればよいですか？
P.S.：この質問はではなく、からのライブコンテストです。
私が試したのは、変数lenを取っていました。配列の長さと配列の長さが異なります。lenはすべての要素をカバーするかどうかをチェックします。

Answer 1

配列の長さをNとし、特有の要素の数をK,K<=Nとしましょう。 値が0,1、...、K-1としましょう。 （私たちは、その後、元の位置に戻ってそれらを置くなど、すべての要素をソートし、その後0と最小値を持つ要素を置き換え、1と第2の最小値を持つ要素できます。これは、O(N*log(N)複雑さを必要とします。）

配列を作りますC[K]、C[i]は、セグメントの値がiの要素の数を保持する必要があります。 Dをセグメント内のいくつかの異なる要素とします。

yを増やしてこのセグメントを拡張すると、C[A[y+1]]が1つ増えます。 C[A[y+1]]が1になる場合、Dを1増やします。

xを増やしてセグメントを縮小すると、C[A[x+1]]が1つ減少します。 C[A[x+1]]が0になる場合、Dを1で減らします。

したがって、D==Kの場合、セグメントにすべての要素が含まれていることがわかります。

今すぐ[0, 0]から開始し、可能なすべての値が含まれるまでセグメントを延長し続けます。それは[0, q]です。 その後、結果のセグメントにすべての可能な値を持つ要素がある間に縮小します。それを[p, q]とする。

[p, q]を1つ右に移動します。つまり、[p+1, q+1]になります。 再度、セグメントを縮小しようとします。など

大まかに言えば、セグメントを左から右に動かし、すべてのステップでそれを縮小してみてください。あなたが最後に到達し、もう左端を動かすことができない場合、あなたは完了です。それはO(N)です。だから一緒に（並べ替えを含む）：O(N*log(N))。