golangで60 questions to solveを説いてみるシリーズ。
今回の問題はtwosum。

two sum

最初の1問。
これって各言語ごとの回答とか、みんなの回答とか見れないのかな。
ここに転がってた。

Brute Force

func twoSum(nums []int, target int) []int {  
    for ni, i := range nums {
        for nj, j := range nums {
            if ni == nj {
                continue
            }
            if i+j == target {
                return []int{ni, nj}
            }
        }
    }
    return []int{}
}

Brute Forceとは、いわゆる総当り攻撃。

複雑性

時間計算量

O( n^2 )

になる。この意味からしてわからない。

O記法

Big O notationと呼ぶらしい。これは成長の程度を表す記法で、最悪の場合のアルゴリズムのコスト関数を表現するために使われる。

成長率の最も高い関数に注目して、例えば上記のような2次以下に成長するものは

O( n^2 )

線形以下に成長するものは

O( n )

と表す。logというのもよく出てくるが、一旦おいておこう。このnを当てはめることができれば、計算量がざっくり試算できるわけだ。

例えば、atcoderであれば、

O( 10^9 )

くらいまでを目安にするといいらしい。

空間計算量

一旦メモリのカウント、と覚える。
今回であれば、固定数の変数がひつようなので、

O( 1 )

となる。

Two-pass Hash Table

func twoSumHash(nums []int, target int) []int {  
    comparisons := make(map[int]int)
    for i, j := range nums {
        comparisons[j] = i
    }
    for i, j := range nums {
        need := target - j
        res, ok := comparisons[need]
        if ok && i != res {
            return []int{i, res}
        }
    }
    return []int{}
}

次に示されている答えがこれだ。
確かにhash tableを使えば見かけ上のloopの回数は減り、計算回数は

O( n )

になる。だけど、hash tableの計算量はなぜO(1)とみなせるのか。O(n)じゃないのか。ちょっとむずかしそうなので、一旦はそういうものとして覚えておこう。

ただし、hash tableを使うと、item数によってテーブルのサイズが変わるため、空間計算量は

O( n )

になる。

One-pass Hash Table

func oneSumHash(nums []int, target int) []int {  
    comparisons := make(map[int]int)
    for i, j := range nums {
        need := target - j
        res, ok := comparisons[need]
        if ok && i != res {
            return []int{res, i}
        }
        comparisons[j] = i
    }
    return []int{}
}

これは若干頭の体操に近いね。

Menu