arrays - 合計が与えられた値と等しくなるように 2 つの要素を見つける

Question

'n' 個の数の 2 つのセットが A と B に与えられます。合計が所定の値 'val' に等しくなるように、A から 1 つの要素と B から 1 つの要素を選択します。

私は次のように解決策を持っています：

セット A とセット B の要素をハッシュし、セット A のすべての要素について、セット B のハッシュに val-arr[i] が存在するかどうかを確認できます。これには O(n) の時間と O(n) のスペースが必要です O(1) のスペースと O(n) の時間のより良いソリューションはありますか?

Answer 1

両方の配列がソートされていないため、他のオプションはありませんが、すべての要素を1つずつ確認します。O(n)したがって、実行時間を下回ることはできません。あなたが使っているアプローチは大丈夫だと思います。

これらの関連記事を読んでください：

2つの配列aとbが与えられます。a1が配列Aに属し、b1が合計a1 + b1 = kの配列Bに属するように、要素のすべてのペア（a1、b1）を見つけます。

合計がkになる配列内の2つの要素を見つけます