1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

//用map辅助查找 时间复杂度O（n）
func twoSum(nums []int, target int) []int {
    hash := make(map[int]int)
    for i := 0; i < len(nums); i++ {
        hash[nums[i]] = i
    }

    for i := 0; i < len(nums); i++ {
        temp := target - nums[i]
        if _, ok := hash[temp]; ok {
            if hash[temp] == i {
                continue
            }
            return []int{i, hash[temp]}
        }
    }

    return nil
}

// 测试
func main() {
    nums := []int{-6, 7, 11, 15}
    target := 9
    fmt.Println(twoSum(nums, target))

    nums = []int{2147483647, -2147483646, 11, 15}
    target = 1
    fmt.Println(twoSum(nums, target))
}