[解決済み] 配列から、和が指定された数に等しい要素の組を求めよ。
2022-06-20 18:57:06
質問
n個の整数の配列が与えられ、数Xが与えられたとき、その和がXに等しいユニークな要素の組(a,b)を全て求めよ。
以下は私の解答ですが、O(nLog(n)+n)となりますが、最適かどうかはわかりません。
int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
i++;
}
j--;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
j--;
}
}
}
どのように解決するのですか?
# Let arr be the given array.
# And K be the give sum
for i=0 to arr.length - 1 do
# key is the element and value is its index.
hash(arr[i]) = i
end-for
for i=0 to arr.length - 1 do
# if K-th element exists and it's different then we found a pair
if hash(K - arr[i]) != i
print "pair i , hash(K - arr[i]) has sum K"
end-if
end-for
関連
-
[解決済み] 簡単な面接問題が難しくなった:1~100の数字が与えられたとき、ちょうどk個の数字が欠けていることを見つけなさい。
-
[解決済み] 32ビット整数のセットビットの数を数えるには?
-
[解決済み] ビッグ・オー、どうやって計算・概算するんだ?
-
[解決済み] 短縮URLの作成方法を教えてください。[クローズド]
-
[解決済み] 地図上のA地点からB地点への道順を計算するアルゴリズムは?
-
[解決済み] Big-O表記とLittle-O表記の違いについて
-
[解決済み】大きなӨ記号は、具体的に何を表すのですか?
-
[解決済み] 幅優先探索を再帰的に実行する
-
[解決済み] 3つ以上の数値の最小公倍数
-
[解決済み] 行または列に 0 が含まれる場合、行列のすべてのセルに 0 を設定します。
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
[解決済み] マージソートの時間および空間の複雑さ
-
[解決済み] nからk個の要素の組み合わせをすべて返すアルゴリズム
-
[解決済み] Big-O表記とLittle-O表記の違いについて
-
[解決済み] フラットな構造から効率的にツリーを構築する方法とは?
-
[解決済み] 一意な(繰り返しのない)乱数をO(1)で?
-
[解決済み] 高次元データにおけるニアレストネイバー?
-
[解決済み] Diff Algorithm? [クローズド]
-
[解決済み] ハッシュテーブルとトライ(プレフィックスツリー)のどちらを選べばいいですか?
-
[解決済み] 2つのキューを使用したスタックの実装
-
[解決済み] バックトラックと深さ優先探索の違いは何ですか?