🐭
NeetCodeをGo言語で挑戦~Two Sum Integer
NeetCode 150のArray&Hashingセクション最後のeasy問題です。
最後は、Two Integer SumをGo言語にて実装してみました。
これまでのチャレンジ
Two Integer Sum
数字の配列と目標となる数字が渡されます。
配列を組み合わせて、目標となる数字のindexの配列を戻す処理です。
例えば、以下のようなインプットとアウトプットがあります。
Input:
array = [3,4,5,6], target = 10
Output: [1,3]
配列の数字を足すと、targetが10になる組み合わせを求めます。
Brute-force or HashMap
アプローチ方法としては、Brute-forceとHashMapを利用した実装を想定しました。
Brute-forceは、2回ループ処理を行います。そのため、n^2となり、効率が悪いです。
そこで、HashMapを利用した実装という方針を設定しました。
いつものようにindexを利用して、実際に解いてみました。
func twoSum(nums []int, target int) []int {
indexMap := make(map[int]int)
// HashMapを作成する。
for i, v := range nums {
indexMap[v] = i
}
// ターゲットの数字の補数を計算して、ハッシュ内を探索する。
for i, v := range nums {
diff := target - v
if j, ok := indexMap[diff]; ok && i != j {
return []int{i, j}
}
}
return nil
}
上記の方法だと、Brute-forceよりも時間計算量が少なくて済むので、効率的です。
まとめ
今回は、HashMapを作成してから、走査を行う処理としました。
実装方針を決めるまで、3分、実装に、4分の合計所要時間は、7分でした。
昔だと、Brute-forceで、無理矢理実装していたのですが、少し大人になって、HashMapを利用するようになりました。
次回以降は、Mediumレベルとeasyよりもレベルが上がりますが、楽しみながら、実装をしていきたいと思います。
Discussion