💡
leetcode"Two Sum"のGo何も理解していない備忘録
概要
leetcodeをやってみよう〜。せっかくなら最近勉強したいと思ってたGoでやろうと思ったが、あまりにもGoを理解していなかったので、戒めの備忘録を残す。
注意）何も理解していないので本当に参考にはならない。
問題
詳細はこちら
(1)配列の宣言を理解していない
まずは最初に書いたコードの一部がこちら
nums := {1,2,3}
target := 10
twoSum(nums, target)
ちゃんと怒られます。
syntax error: unexpected {, expecting expression
Pythonの感覚となんちゃってGoの知識で宣言していました。
正しくは下記
nums := []int{1,2,3}
target := 10
twoSum(nums, target)
このレベルかよ...と思った方。このレベルです。
(2)map
愚直に問題を解くと、あらゆる要素を２つ取り出し、合計して確かめれば良い！ という総当りになってしまう。つまり、nums = [1,2,3,4]という値のとき、1とそれ以外、２とそれ以外、...と計算していくと、計算量が
どうやって書くの????
これに関してはハッシュを用いることが有効であると考えた。
作成したコード
package main
import "fmt"
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for i, j := range nums {
m[j] = i
if k, check := m[target-j]; check {
return []int{k, i}
}
}
return nil
}
func main() {
nums := []int{1,2,4}
target := 6
fmt.Println(twoSum(nums, target))
}
- iにnumsの順番、jにnumsの要素が渡される
-
if k, check := m[target-j]; checkでは、kにm[target - j]、つまりm[j]+m[k]=targetとなる要素がmに含まれているかを確認する。ある場合はcheck = true、ない場合はcheck = falseとなる。- 今回の
nums = {1,2,4}では、j = 1の場合m[5]は存在しない。j = 2ではm[4]は存在しない（j = 2の段階ではm[4]は含まれていない）j = 4ではm[2]は存在するため、[1, 2]を返す
- 今回の
しかし、これは不正解である...
正解コード
package main
import "fmt"
func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for i, j := range nums {
if k, check := m[target-j]; check {
return []int{k, i}
}
m[j] = i
}
return nil
}
func main() {
nums := []int{3,2,3}
target := 6
fmt.Println(twoSum(nums, target))
}
正解コードと自作コードの比較
- pointはmap関数の仕組み。map関数は重複を回避するような構造であるため、例えば`nums = []int{3,3}のような場合、正解にたどり着くことができない。
- なので重要なのはmapに代入するタイミングである。２つの要素の合計値がtargetになるかどうかの判定を行ったあとで、mapに追加することで同じ要素が含まれているような場合でも回避することができる。
感想
疲れた。むずい。でも、気持ちいい
leetcodeはすぐ答えを見ようとする自分には調べるクセがついて良さそう
Discussion