3

int の任意Trueのリストがあり、合計が 0 になるペアがリストに存在する場合に戻ります。

n*log(n) の複雑さでソリューションを作成できました。以下に簡単なスケッチを示します (もっと簡単な方法があります。以下を参照してください)。

  1. 配列をソートします。最初の要素へのポインターを設定します。
  2. ポインターの要素 (最初に呼び出す) と配列の反対側の要素 (最後に呼び出す) を調べます。最初の要素の大きさが最後の要素より大きい場合は、最初の要素を削除し、ポインターを最後の要素に移動します。それ以外の場合は、(可能な) 合計を探して、配列を逆方向に反復処理を開始します。
  3. 合計が見つからない場合は、ポインターを次の要素に移動し、2 を繰り返します。

上記の説明は重要ではありません。明らかに、辞書を使用する別のソリューションがあります。誰かが私を啓発できますか？

4

3 に答える 3

3

要素が-xとxの場合、合計は0になります。すべての要素を繰り返し処理し、値を辞書内に保存します。xがある場合は、-xが設定されているかどうかを確認してください。

そしてところで、あなたの解決策はn * log（n）+nでありn* log（n）ではありません</nitpick>:)

于 2013-03-13T14:46:54.183 に答える
1

key=nとvalue=0-nを辞書に追加します。辞書にすでに0-nキーとして含まれている場合->ペアが見つかりました。

于 2013-03-13T14:45:52.920 に答える
1

ハッシュマップ データ構造を使用すると、O(n) 時間/空間の複雑さを簡単に実現できます。

  1. すべての要素を反復処理し、それらをハッシュマップに配置します (ハッシュマップ操作の挿入、検索、削除の償却時間の複雑さが O(1) であることを考慮すると、時間の複雑さは O(n) です)。
  2. すべての要素を繰り返し処理し、ハッシュマップに逆の値が含まれているかどうかを 1 つのチェックごとに繰り返します (つまり、ハッシュマップに -V 値が含まれている場合は、値ごとに V チェックを行います)。時間計算量は再び O(n) です。

O(n) + O(n) = O(n)

于 2013-03-13T14:52:44.100 に答える