Two Sum

1. 原文

   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].

2. 翻译

   输入：整数数组，目标值

   输出：数组中的两个索引，该两索引对应的值之和为目标值

   假定 ：每组数据只有一个解且同一元素只能使用一次

3. 举例：

   输入：整数数组：[2, 7, 11, 15]，目标值：9

   输出：[0,1]

Solution：

1. 将数组里面任意两个数据进行两两匹配，最多执行次数为\(\frac{n(n-1)}{2}\)，时间复杂度为 \(O(n^2)\)

        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}
                    }
                }
            }
            panic("该测试数据无解")
        }
   

2. 用一Hash表[val]index[值]序号来存放数组的数据，当在字典中找到 target - curVal 的时候即可得到 curVal + val == target 的答案，时间复杂度为 \(O(n)\)

        func twoSum(nums []int,target int)[]int{
        	viMap := make(map[int]int)
            for i := 0; i < len(nums); i++ {
                if j, isExist := viMap[target-nums[i]]; isExist {
                    return []int{i, j}
                } else {
                    viMap[nums[i]] = i
                }
            }
            panic("该测试数据无解") 
        }
   

   总结

   在必要时候可以将数组转成 Hash 表提升查询效率，减少时间复杂度。