arrays - a --b=kとなるようにソートされた配列で2つの整数を見つけます

Question

整数kとソートされた配列A（正の数と負の数の両方で構成できます）が与えられた場合、Aから2つの整数を出力a-b=kします。O(n) timeO(1) space

O（n logn）解決策：

1. 配列をトラバースします。O(n)
2. 要素a[i]の場合、a[i]+kバイナリ検索を使用して配列を検索します。O(log n)

合計時間：O(n logn)

O（n）ソリューション：

1. 配列のすべての要素をハッシュテーブルに格納します。O(n)
2. 要素a[i]について、ハッシュテーブルのa [i]+kかどうかを確認します。O(1)

合計時間：O(n)

スペース：O(n)

しかし、彼は余分なスペースを備えたO(n)ソリューションを望んでいO(1)ます。誰か考えがありますか？

Answer 1

2つのインデックスポインタ（左と右）を作成し、両方を配列の先頭（0）に初期化します。a [Left] + k> a [Right]の場合は右にインクリメントし、そうでない場合は左にインクリメントします。等しいときに停止します

Answer 2

アイデアは、配列に2つのポインター（たとえばaとb）を使用することです。元々、どちらも先頭を指しています（a=b=0）。

の場合ar[a]+k < ar[b]、あなたは前進します。

の場合ar[a]+k > ar[b]、bを進めます。

の場合ar[a]+k == ar[b]、解決策が見つかりました。

それがO(n)時間とO(1)空間です。