【LeetCode通关全记录】1. 两数之和
题目地址：1. 两数之和
解法1：暴力枚举（时间换空间）
估计所有人看到这道题想到的第一个方法都是暴力枚举，即对数组中的每一个数都遍历一次该数组，寻找是否有满足num1 + num2 == target的数。这种方法比较简单，是一种用时间换空间的方法。
func twoSum(nums []int, target int) []int {
if nums == nil {
return []int{}
}
for index1, num1 := range nums {
for index2, num2 := range nums {
if num1 + num2 == target && index1 != index2 {
return []int{index1, index2}
}
}
}
return []int{}
}
执行用时: 16 ms（超过57%的Golang提交记录）
内存消耗: 4.6 MB（超过91%的Golang提交记录）
时间复杂度：O(n^2)，对数组中的每一个数都需要遍历两次数组，所以算法的执行时间与问题规模为平方关系；
空间复杂度：O(1)，只使用了常数个数的存储空间。
解法2：哈希表（空间换时间）
除了暴力枚举之外，还有一种不太好想到的方法：用空间换时间。我们可以边遍历数组边将数组元素num作为key、num的下标作为value放入哈希表中，如果在之后的遍历中遇到target - num在哈希表中的情况，说明找到了满足要求的数，直接返回遍历到的数据的下标和该key对应的value即可。注意要先比较再插入哈希表，以此避免num和自身比较。
func twoSum(nums []int, target int) []int {
if nums == nil {
return []int{}
}
t := make(map[int]int)
for index, num := range nums {
if i, ok := t[target-num]; ok {
return []int{i, index}
}
t[num] = index
}
return []int{}
}
执行用时: 4 ms（超过98%的Golang提交记录）
内存消耗: 4.2 MB（超过35%的Golang提交记录）
时间复杂度：O(n)，只需要遍历一次数组；
空间复杂度：O(n)，哈希表的长度与问题规模成正比。
