【LeetCode】1. Two Sum

概要

一番最初の

func twoSum(nums []int, target int) []int {
    for parentIdx, parentVal := range nums {
        for childIdx, childVal := range nums {
            if (childIdx == parentIdx){
                continue
            }
            if (childVal + parentVal == target){
                return []int{childIdx, parentIdx}
            }
        }
    }
    return nil
}

改善策

現状、配列の各要素について、他のすべての要素との合計をチェックしているのでO(n²)の時間複雑度を持っています。 これを改善するために、ハッシュマップ（Goではmapと呼ばれます）を使用して、一度のループで問題を解くことができます。 これにより時間複雑度はO(n)になります。

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        // 補数を求める
        complement := target - num
        // mapのkeyに補数があるか
        if j, ok := m[complement]; ok {
            return []int{j, i}
        }
        // なければmapのkeyにnum、valにindexを入れる
        m[num] = i
        fmt.Println(m)
    }
    return nil
}

このコードは、各要素を訪れるときに、それが必要な補数（目標となる合計からその要素を引いたもの）が既にマップ内に存在するかどうかをチェックします。存在する場合、それは目標の合計を構成する2つの数が見つかったことを意味します。存在しない場合、その要素をマップに追加します（キーは要素の値、値は要素のインデックス）。

まとめ

ループが二重、O(n²)だと思ったら思ったらハッシュマップが使えないか調べてみる。