1. Two

問題

数字の配列と一つの数字が与えられるため、足すと与えられた数字になる 2 つの数字を配列から探し、そのインデックスを答えよ、という問題。なお解は必ず一つしかない。 https://leetcode.com/problems/two-sum/description/

初手

わざわざ時間計算量 O(n^2) にならないようにできるかな？って書いてあるけど二重ループによる総当たりしか浮かばずこれで通した。説明するべくもないけど、単に i, j を使って配列の先頭から 2 つの数字を足していき、target と等しくなれば終了しています。総当たりです。最悪計算量は O(n^2) です。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{}
}

最終手

答えを見て、1 日空けてから解いたら自力では解けませんでした。明日もやらねば。考え方は、1 ループ目で nums の値をキーに、nums のインデックスを値に持つ map を作ります。 2 ループ目で、target - nums[i] を計算しておき、その値が 1 ループ目で用意した map のキーにあれば、そのときのインデックスが答えになります。ただし、i == j だと同じ値を 2 度利用しているだけなので、 i != j とする必要があります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func twoSum(nums []int, target int) []int {
    hm := make(map[int]int, len(nums))
    for i, v := range nums {
        hm[v] = i
    }
    for i, v := range nums {
        c := target - v
        if j, ok := hm[c]; ok && i != j {
            return []int{i, hm[c]}
        }
    }
    return []int{}
}

これは最悪でも O(n*2) ですね。nums を 2 回ループする以上の処理は必要ありません。実際は Go の map はハッシュテーブルで実装されており、その探索に O(1)を要するため、もう少し計算量がかかりますが無視しましょう。