私はこの質問を見ましたが、時間とスペースの制約を考えると、2番目の部分を行う方法がわかりません:
値の配列が与えられた場合、相互の k インデックス内に 2 つの重複があるかどうかを返すアルゴリズムを設計およびコーディングしますか? k 個のインデックスで、互いにプラスまたはマイナスの l (値) 内にあるか? O(n) の実行時間と O(k) のスペースで、後者もすべて実行します。
k と a[i] のインデックスの差があるすべての値を調べずに、値のウィンドウ サイズ内に特定の値の重複があるかどうかを知ることは不可能に思えますが、a[i] は大きい可能性があるため、 O（n ^ 2）かかります。O(n)でできますか？