LeetCodeの最初の問題、「Two Sum」を見てみましょう。
問題の説明は以下の通りです。
整数の配列numsと整数のターゲットが与えられた場合、
ターゲットになるように2つの数のインデックスを返します。
入力には必ず 1 つの解が存在し、同じ要素を 2 回使用することはできません。
答えはどの順番でも返せます。
では、ここで例を見てみましょう。
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
可視の通り、nums配列の 0 番目の要素 (2) と 1 番目の要素 (7) の和が target 値の 9 になるため、出力はこれらの 2 つの要素のインデックスで構成される配列になります: [0, 1]。
問題で返すべきものが何であるかが分かったら、解く方法を考えましょう。
ブルートフォース法で考えられる全ての組み合わせを生成し、それぞれの組み合わせが target になるかどうかを確認していくと、時間計算量が O(n²) になってしまいます。この解法は効率が非常に悪くなってしまいます。
したがって、今回はハッシュテーブルを使った解法アプローチを採用します。これにより、時間計算量を O(n) に削減できます。
Pythonコードはこちらです。
6行目で、「lookup」 という名前の辞書型変数 (ハッシュテーブル) を使っていることが確認できます。
次に、nums 配列全体を走査します。 「ターゲットから現在の要素を引いた値」が lookup 変数に存在しない場合、「ターゲットから現在の要素を引いた値」をキーとし、現在のインデックスを値として、lookup 変数にキーと値のペアを追加します。
そして、「ターゲットから現在の要素を引いた値」が lookup 変数に存在する場合、答えが見つかったことを意味します。このとき、lookup 変数から「ターゲットから現在の要素を引いた値」 をキーとして取得した値と、現在のインデックスとで構成される配列を直接返します。
では、この解法の時間計算量と空間計算量を見てみましょう。
時間計算量
配列 nums 全体を見て回るため、O(n) です。for ループ内では、ハッシュテーブル変数にキーが存在しているかを確認したり、ハッシュテーブル変数にキーと値のペアを追加したりなどの操作を行いますが、これらの操作はどちらも一定時間で実行できます。したがって、この解法の全体的な時間計算量は O(n) になります。
空間計算量
ハッシュテーブル変数が必要なので、最悪の場合、nums 配列のすべての要素がハッシュテーブルに格納されます。したがって、空間計算量は O(n) になります。
Javaコードはこちらです。
解法自体は基本的に同じです。
ハッシュマップのキーと値の型は、Integer (整数) として定義する必要があります。また、for ループ内で返り値がない場合は、null を返します。しかし、この問題では必ず解が 1 つ存在することが保証されています。
説明動画とコードへのリンクを以下に示します。ご自由にご確認ください。