leetcode-两数之和

题目
给定一个整数数组nums和一个整数目标值target，在数组中找出两数之和为目标值target的元素下标,返回下标数组。
示例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]

分析
给定数组，常规思路是遍历数组，两层循环可以轻松搞定，时间复杂度O(N^2) ，空间复杂度O(1),直接pass，然后考虑以空间换时间，使用map来做，map的底层是hash实现，时间复杂度为O(N)，空间复杂度O(N)

题解

• 暴力解法, 循环遍历

func twoSum(nums []int, target int) []int {
    var result []int

    if len(nums) <= 0 {
        return result
    }

    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                result = append(result, i, j)
            }
        }
    }
    return result
}

测试结果

63/63 cases passed (36 ms)
Your runtime beats 5.08 % of golang submissions
Your memory usage beats 98.92 % of golang submissions (3.3 MB)

• Hash算法
  起点必须是遍历数组，从元素x开始，需要找到匹配的target-x的值，这里使用map，也就是hash索引，时间复杂度为O(1)

func twoSum(nums []int, target int) []int {
    var nummap = make(map[int]int)
    for k, v := range nums {
        if p, ok := nummap[target-v]; ok {
            return []int{k, p}
        }

        nummap[v] = k
    }
    return nil
}

63/63 cases passed (5 ms)
Your runtime beats 56.84 % of golang submissions
Your memory usage beats 34.6 % of golang submissions (4 MB)

这里存在一个问题，为什么使用数组元素作为map的key，而不是用下标做，这是因为，如果使用下标做key的话，我们在map中匹配target-v的元素时，不能直接使用map查找方法来锁定匹配值，需要遍历map，这无疑又增加了一次时间复杂度，因此最快是用数组元素作为key。