2つのパターンの合計についてn（n + 1）/ 2を計算するにはどうすればよいですか？

Question

11を言う、私はnまでの範囲の配列があると、それは、今

U = 1 2 3 4 5 6 7 8 9 10 11

であり、Iは、アレイA（Uのサブアレイ）を有する：

1 3 4 9 

アレイ-B（Aと共通の何もUの他のサブ配列）：すべてのこれらの3セットがSORある

2 5 6 10 

留意されたいです。テッド。

(a[i+1]-a[i]-1)ごとにn(n+1)/2を計算する必要があります。ここで、iは配列のインデックスであり、aは一般化された配列です。

また、両端のコーナーケースも考慮してください。最初の桁から1を引いてからn(n+1)/2を計算し、最後の桁を11から減算してからn（n + 1）/ 2を計算します。

たとえば、集合Aの場合：私たちはここに (3-1-1)* + (4-3-1)* + (9-4-1)* + Corner Cases コーナーケースを取得：(1-0)* + (11-9)*

のx *は、x（X + 1）セットBについても同様/ 2

を意味します。私たちは、(5-2-1)* + (6-5-1)* + (10-6-1)* + (2-1)* + (11-10)*

今、私は計算する必要がいますO（1）の複雑さの集合Aと集合Bを用いた（AUB）の解。これを行う方法はありますか？

複雑さがO（N）の場合、2つの配列をマージして上記の式を適用するだけです。そこで解決策

A U B : 1,2,3,4,5,6,9,10 

= (9-6-1)*+ (11-10)*

Answer 1

はたぶん、あなたは伸縮式の和 （here's an exemple）を使用することができます。 各ループ（配列の各インデックス）であなたが前のループに追加番号substractので、私はそれについて考える：

u[2] - u[1] - 1 + u[3] - u[2] - 1 + u[4] - u[3] - 1 + ... + u[n] - u[n-1]- 1 

あなたを与える：

- u[1] - 1-...-1 + u[n] 
= u[n] - n - u[1] 

また、AとBをあなたの数字を注文するので、Additionaly

n = lenght(A) + length (B) 

：なぜだ共通点は何もない

u[1] = min (A[1] , B[1]) 
u[n] = max (A[length[A]] , B[length[B]]) 

だから我々はそれを持っている：

Solution = max (A[length[A]] , B[length[B]]) - lenght(A) - length (B) - min (A[1] , B[1]) 

私はこの問題であなたを助け願っています。 （私が英語でいくつかの間違いをした場合は申し訳ありません）。