解答と解説: Two Sum

「問題演習: Two Sum」の解答編です。問題出題ページの最後に、下記の 2 点について考えるように提案しました。このような質問は実際の面接時に聞かれますので、これらを考えた上で解答例を見てください。

• ループを 2 つ使った方は、1 つしか使わずに解く方法も考えてください。
• ループの数の違いによって、どちらの解法にどのようなメリットがありますか。

解答例

Javaでの解答例です。

解説

上記の 1 つのループを用いた解法では Map を用いて、現在の値を使用した場合の不足分target - nums[i] をキーとし、現在のインデックス i を値に保存しています。その後ループで i をインクリメントし、他の配列 nums の値が Map のキーに既に登録されていないか確認します。もし既に登録されていた場合は、現在のインデックスと過去の値のインデックスを返せばよいです。時間計算量はループが 1 つなので O(n)、空間計算量は最大でも n - 1 個の値しか Map に保存しないので O(n) になります。

次に 2 つのループを用いた解法も紹介しておきます。おそらくこの問題を初めて見た方は、まずこの解法に辿り着いたと思います。この解法は全探索、つまり全ての値を調べる手法で少々効率が悪いです。例えばこのようなプログラムです。このプログラムの時間計算量は O(n^2) で、特別に何かをメモリに保存する必要はありません。つまり空間計算量は O(1) です。


ここで計算量の概念を知らない方に、念のため説明しておきましょう。時間計算量とはプログラムの処理数のことで、空間計算量とは記憶領域使用量です。どちらとも小さい方が良いです。計算量は O(1) や O(n)、 O(n^2) という O-記法で表記されます。ざっくり言うと O(n) は n 回の計算で解答を見つけることができるという意味です。O(n) は n の値の増大に対し線形関数的に値が増えますが、下記のように O(n^2) は平方関数的に増加します。一方、O(1) は n の値によって変化することはありません。

• O(1): 1, 1, 1, 1, 1, 1...
• O(n): 1, 2, 3, 4, 5, 6...
• O(n^2): 1, 4, 9, 16, 25, 36...

今回の Two Sum 問題に当てはめると、配列 nums の長さが n に相当します。n 個の要素を 1 つのループを用いて一つ一つ見ていく場合は n 回の計算になるので O(n)、一方 2 つのループを用いた解では (n - 1) * ((n - 1) - 1) = n^2 - 3n + 1 回の計算をすることになります。ただし、先ほど示したように n の増え方は n^2 の増え方と比較すると小さいので n^2 だけに注目します。つまり 2 つのループを用いが場合の時間計算量は O(n^2) です。

ただし、空間計算量は 1 つのループを用いた解では O(n) で、2 つのループを用いた場合 nums の長さに左右されないので O(1) でした。空間計算量だけを見れば O(1) の方が優れていますが、時間計算量「O(n) vs O(n^2)」と空間計算量「O(n) vs O(1)」を比較した場合、前者の方が配列 nums の長さが長くなった時に与える影響は大きいです。そのため、特にメモリを使用するなとかいう制限がない限り、全体として O(n) vs O(n^2) の比較で勝る方が優れた解法ということになります。つまり 1 つのループを用いた解答が優れているということになります。

以上の点を押さえておけば概ね OK です。仮に私が採用面接官としてこの問題を出したとしたら、以上の点は少なくとも口頭で説明してもらうと思います。
---
シリコンバレーでエンジニアとして就職するには、アルゴリズムやプログラミング、システムデザインの問題が出題される面接を突破する必要があります。本サイトでは、シリコンバレーでエンジニアとして働き、面接官としての経験も豊富な筆者が、面接への対策に関する情報を配信しています。