範囲内の重複を見つけるためのより効率的なアルゴリズムアルゴリズム

Question

this質問には、指定された範囲の範囲のリストの重複を見つけるアルゴリズムが含まれていました。しかし、私の状況ではn^2ペアのフォームの範囲にグループ化するとnの整数のリストがあります。例えば、array[i]とarray[j]を整数配列から取ると、(array[i]-array[j],array[i]+array[j])は範囲を作る。しかし、提案されたアルゴリズムを実装するためには、解はメモリの複雑さがO(n^2)である。それはさらに（メモリの点で）最適化できますか？

例： Iが大きい範囲(l,r)を有し、そしてIはranges.For例のリストのうちの少なくともいずれかに(l,r)位置にどのように多くの整数を見つける必要があり、指定された整数配列は{1,2,3}あります。可能な範囲はすべて(2-1,1+2), (3-1,1+3), (3-2,3+2)です。 (l,r)が(2,7)であるとします。その後、少なくともには(2,5)が存在するため、答えがあります。

Answer 1

配列をソートすることから始めます（まだソートされていない場合）。考慮する価値のある範囲は、j == i-1です。次の配列考える理由を理解することは

：

{2,3,5,8} 

は、その後の可能な範囲は以下のとおりです。j < i-1ための範囲は、常に厳しいj == i-1範囲のサブセットなので、ものであることが

i=3 j=2 ==> (8-5,8+5) = (3,13) 
i=3 j=1 ==> (8-3,8+3) = (5,11) 
i=3 j=0 ==> (8-2,8+2) = (6,10) 

i=2 j=1 ==> (5-3,5+3) = (2,8) 
i=2 j=0 ==> (5-2,5+2) = (3,7) 

i=1 j=0 ==> (3-2,3+2) = (1,5) 

お知らせ範囲を考慮する必要はありません。したがって、O（n）の範囲を考慮する必要があります。