数组-两数之和

/*
 * @Description:
 * @Author: huacong
 * @Date: 2020-03-11 23:21:39
 * @LastEditTime: 2020-03-12 00:25:31
 * @LastEditors: huacong
 */
package main

import "fmt"

//暴力破解
//时间复杂度O(n²)
func twoSum(arr []int, target int) []int {
    for key, val := range arr {
        for k, v := range arr {
            if val+v == target {
                return []int{key, k}
            }
        }
    }
    return []int{}
}

//一遍哈希
//时间复杂度O(n)
func twoSum2(arr []int, target int) []int {
    maps := make(map[int]int)
    for i, v := range arr {
        if k, ok := maps[target-v]; ok {
            return []int{k, i}
        }
        maps[v] = i
    }
    return []int{}
}

func main() {
    arr := []int{2, 20, 2, 15}
    res := twoSum(arr, 22)
    fmt.Println(res)

    res1 := twoSum2(arr, 22)
    fmt.Println(res1)

}