【LeetCode】1. Two Sum (Easy)

【最初に】

LeetCodeのアルゴリズムの最初の問題を解いてみます

https://leetcode.com/problems/two-sum/

【問題】

与えられたint配列に対して足すと指定の数値になる配列内の2つの数値のインデックスを返せ。入力には必ず解が1だけある前提。配列の同じ要素は使わないこと。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

【とりあえず】

単純に思いつくのは、とりあえずfor文をぶん回して足していって答えに辿り着いたら終了するパターン。

でもこれはたぶんダメダメなやつ

解答を見ると、上の例だと最後の1個まで解が見つからない場合、ループをn回実行して、各要素ごとにn回ずつ回すので、時間計算量はO(n^2)になるとのこと。

【違うパターン】

ヒントを見るとhashmapを使ったらとあるので、違うパターンを試してみる

最初に数字をkeyに、配列のインデックスをvalueにした連想配列を作る。次にもう一度配列を回して、補数がマップにあるかどうか検索。存在する場合は結果を返して終了する。

速くなった！（メモリは増えたけど）

時間計算量はO(n^2)からO(n)に減少（O(2n)と書かない理由はこちらを参照：https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0）ただし、空間計算量は配列の分だけmapとしてメモリに格納するのでO(1)からO(n)に増える

 【さらに違うパターン】

↑だと配列のループを2回回しているけど、解答見るとループを1回で済ませる方法もある

 ループを回していって、マップに補数がなければ格納。順にループを回していって過去に追加したマップの値と比較して発見すればインデックスを返して終了する。

【最後に】 

気分転換に最初の1個目をやってみましたが面白いですね。アルゴリズムはこれまであまりきちんと勉強して来なかった（正確には大学でやってるはずだけど真面目に授業受けてなかった）ので、もうちょっと続けてみようかと思います。ちなみにC++も大学でやってるはずだけど...（以下同文）C++の作法とかよくわかってないので、その辺りはご容赦を。