Two-Sum-事前ソート最適化アルゴリズムの設計
🧩事前に並べ替えられた入力を昇順または降順で受け取ることにより、2合計ソリューションの実行時間を最適化することは可能ですか？
🚀オリジナルの2つの合計
同じアイテムを2回選択できないようにしながら、個々の容量が合計容量と完全に等しくなるアイテムが2つあるかどうかを判断します。
- 入力：合計容量を表すIntと、アイテムの個々の容量を表すIntの配列。
- 出力：2つのアイテムが合計容量に等しくなる可能性があるかどうかを表すブール値。
- 時間計算量：線形成長、 $O(n)$
- スペースの複雑さ：線形成長、 $O(n)$
サンプル
入力： [4, 5, 2, 6]
- 総容量：
10 - 期待：
true
入力： [4, 5, 2, 5]
- 総容量：
10 - 期待：
true
入力： [4, 5, 2, 7]
- 総容量：
10 - 期待：
false
擬似コード
searchSetすでに調査済みのアイテムを保存するセットを作成します。アイテム容量の入力配列を反復処理します。
2a。
targetCapacity現在のアイテムのを検索します。totalCapacity - itemCapacity2b。
searchSetが含まれている場合は、targetCapacityを返しtrueます。2c。それ以外の場合は、
itemCapacityをに追加しsearchSetます。false一致するものが見つからずに入力全体が繰り返された場合に戻ります。
🏗️プレソート
- 新しい変数を保存する
lastTargetCapacity - 現在の
itemCapacity<の場合、lastTargetCapacity可能な2つの合計はありませんfalse。
すなわち
入力： [6,2,1,0]
- 総容量：
9
反復
targetCapacity = 9 - 6、lastTargetCapacity= 3itemCapacityの2<lastTargetCapacityのため、falseを返します3。
回答
入力配列が昇順または降順で事前にソートされている場合、TwoSumソリューションは実行時のパフォーマンスに合わせて最適化できます。
バイナリ検索を使用してtargetCapacity上記を検索すると、対数で実行されます。$O(logn)$、平均実行時間。これは、線形で実行される上記の擬似コードよりも高速です。$O(n)$、反復とハッシュを使用したランタイム。
入力に並べ替えが指定されていない場合、より高速に並べ替えて検索することはできません。 $O(n)$。できる最善のことは$O(nlogn)$ クイックソートやバイナリ検索などの戦略で。
参照：スタンフォード-2つの合計の説明
はい、で2和問題を解くことができます $O(n)$時間、番号がソートされた順序で表示される場合。それを行う方法については、私の他の回答を参照してください。線形スキャンが含まれます。これは漸近的に最適です。$O(n)$ 入力を読み取る時間さえあり、問題を解決するには入力全体を読み取る必要がある場合があるため、それ以上の漸近的な改善はありません。