乐扣1:两数之和（tag:哈希）

前言：决定从今天刷LeeCode，选择了算法篇，因为之前觉得学了算法很长时间却没什么操练。可能刷起来比较慢，因为还有其他一些事情要做。总之，希望我的flag不要倒，多做题。
下面是乐扣的第一题。

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

第一眼看到题目想到的就是遍历数组，但是时间复杂度较高。然后想，能不能先把无序数组排序然后利用二分法查找，可是排序的时间复杂度已经和遍历数组一样了。这两种办法都不好，然后看到题目的tag是数组和hash，可能需要用哈希表的方法？其实看到哈希表有点懵，因为我是写go的，好像没遇见过go的哈希表？谷歌了一下才知道，原来go的map已经实现了hash的作用。那用map就可以了。

因为数组存的是值到下标的对应关系，如果给定一个target，对于某个数组中的值value，找到target-value的值对应下标的最快方法大概就是实现给定某个值快速找到它再数组中的下标，那么hash就是数组的值到这个值在数组中的下标的对应关系。

实现

初版代码

代码如下

func twoSum(nums []int, target int) []int {
    // value-当前值的结果到当前值的下标的映射，因为下标是从0开始的，所以为了避免map的歧义，在下标上加上1
    map1:=make(map[int]int)
    result:=make([]int,2)
    for idx:=0;idx<len(nums);idx++{
        value:=nums[idx]
        rest:=target-value
        map1[value]=idx+1
        if map1[rest]!=0{
            result[0]=idx
            result[1]=map1[rest]-1
            return result
        }
    }
    // 如果找不到
    return result
    
}

下标为0与map中key不存在返回0的冲突

然后提交说失败了，对于([2,4],6)这样的输入，答案为错误的[0,0]。我发现是if map1[rest]!=0那一行出错了，因为2对应的下标就是0，而我这里想判断的是如果map中不存在这个key的话，然后就改造程序：map存值到下标加1的对应关系，如下：

func twoSum(nums []int, target int) []int {
    // value-当前值的结果到当前值的下标的映射，因为下标是从0开始的，所以为了避免map的歧义，在下标上加上1
    map1:=make(map[int]int)
    result:=make([]int,2)
    for idx:=0;idx<len(nums);idx++{
        value:=nums[idx]
        rest:=target-value
        map1[value]=idx+1
        // 忽略重复的数据
        if target-value!=value && map1[rest]!=0{
            result[0]=idx
            result[1]=map1[rest]-1
            return result
        }
    }
    
    // 如果找不到
    return result
    
}

不同位置的相同值可以参与计算

运行显示，对于([3,3],6)这样的输入结果不对，原来是忽略重复数据那里。我判断应该是不能把数组中的用一个数（即下标相同的）计算两次，而不是两个不同下标的相同数不能相加。如果想实现这个的话，把判断target-value是否存在放在往map里添加值就可以了。
如下：

func twoSum(nums []int, target int) []int {
    // 当前值加上当前下标+1 到下标+1的映射，
    // 因为下标是从0开始的，所以为了避免map的歧义，在下标上加上1
    map1:=make(map[int]int)
    result:=make([]int,2)
    for idx:=0;idx<len(nums);idx++{
        value:=nums[idx]
        rest:=target-value
        if  map1[rest]!=0{
            // 忽略重复的数据，即自己和自己相加
            if idx+1==map1[rest]{
                continue
            }
            result[0]=idx
            result[1]=map1[rest]-1
            return result
        }
        map1[value]=idx+1
    }
    
    // 如果找不到
    return result
    
}

这次总算通过啦。

总结

修改了几次，都是因为考虑不周引起。写程序测试时最好多考虑写异常路径。
看了一下该问题的评论，用go写的人并不多，然后有一个地方可以优化，判断map中是否存在某值可以用如下代码，这样下标为0与map中key不存在返回0的冲突将不会存在。

if value, ok:=map1[key];ok{}

go的map效率很高，已经实现了哈希表的高效。再很多算法都可以用到这个数据结构。
前期思考远比代码实现重要。

最终版

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    // 当前值到下标的映射，
    map1:=make(map[int]int)
    result:=make([]int,2)
    for idx:=0;idx<len(nums);idx++{
        value:=nums[idx]
        rest:=target-value
        // 先判断有没有值存在再往map里面添加，
        // 避免输出类似([3,3],6)出错
        if  restvalue,ok:=map1[rest];ok{
            // 忽略重复的数据，即自己和自己相加
            if idx==restvalue{
                continue
            }
            result[0]=idx
            result[1]=restvalue
            return result
        }
        map1[value]=idx
        
    }
    
    // 如果找不到
    return result
    
}

func main(){
    nums := []int{2,4,11,15}
    r:=twoSum(nums,6)
    fmt.Println("----------------",r)
}