重複の可能性:
配列から三角形を見つける
このフォーラムでこのインタビューの質問を見つけました: http://geeksforgeeks.org/forum/topic/check-for-triangular-triplet
以下の説明をコピーしています (礼儀は geeksforgeeks.org と元のポスターのカピル)
N 個の整数からなるゼロ インデックスのベクトル A が与えられます。
トリプレット (P、Q、R) は、次の場合に三角形です。
A[P] + A[Q] > A[R],
A[Q] + A[R] > A[P],
A[R] + A[P] > A[Q].
たとえば、次のようなベクトル A を考えます。
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
トリプレット (0, 2, 4) は三角形です。
プログラムを書く:
int triangle(const vector<int> &A);
N 個の整数で構成されるベクトル A が与えられた場合、このベクトルに三角トリプレットが存在する場合は 1 を返し、そうでない場合は 0 を返します。
編集: 入力ベクトルは変更しないでください。また、O(1) のスペース要件があるため、配列をコピーすることはできません!
と仮定する：
N は範囲 [0..100,000] 内の整数です。ベクトル A の各要素は、範囲 [-2,147,483,648..2,147,483,647] 内の整数です。
たとえば、次のようなベクトル A が与えられます。
A[0] = 10 A[1] = 2 A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
上記で説明したように、関数は 1 を返す必要があります。
もう一つの例：
次のようなベクトル A が与えられた場合
A[0] = 10 A[1] = 50 A[2] = 5
A[3] = 1
関数は 0 を返す必要があります。
予想される最悪の場合の時間の複雑さ: O(n log n) 予想される最悪の場合の空間の複雑さ: O(1)
明らかに配列をソートすることはオプションではありません。この問題を解決する方法について何かアイデアはありますか?