[1日目]　Two Sumを解いてみた

はじめに

本日からジーツファクトリーメンバーのききがよりステップアップするための日記としてアルゴリズム問題を解いた感想やアプローチ方法など記していきます。 毎日１つの問題を解いて行きたいと思います！目指せ100日！

問題の内容

numsという数字が入っているリストとtargetという変数があります。numsの中の数字を足し合わせてtarrgetになるインデックスをoutputに格納して表示させる問題です。

アプローチ方法

 

1. 1. ブルートフォース

ブルートフォースですべての組み合わせを調べる方法。この場合、nested loopを使用するためO(n^2)になる。  

1. 1. Hash map

ブルートフォースの欠点を改善するためにHash mapを使用します。この場合はO(n)です。 以下のポイントで解いていきます。  

• num_dictという辞書を作成
• enumerateを用いてnumsを繰り返す。
• complementという変数にtarget-numを格納
• もしnum_dictにcomplementと同じ数字があったら、現在のインデックスとnum_dictのバリューがcomplementをリストに格納して返す
• num_dictに現在のインデックスとnumを格納

まとめ

ベアを見つける問題はブルートフォースよりhashを使用したほうが効率的に解けることを学びました。 HashMap（辞書）は、キーと値のペアを高速に格納・検索できるため、特に以下のようなシナリオで非常に効果的です。  

• 文字列中の各文字の出現回数を数える
• リスト内で重複する要素があるかを確認する。
• 2つのリストから共通する要素を探す場合。