给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和(sum)为目标值 target 的那 **两个** 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
先使用最先想到、可能是最笨的方法，然后，我们一步一步优化。
方法一：暴力法
最容易想到的方法就是，从第一个数开始遍历，依次查看数组剩余的数与它的和是否是target。两层循环。
代码如下
//golang
func twoSum(nums []int, target int) []int {
for i, v := range nums {
for j := i + 1; j < len(nums); j++ {
if nums[j] == target - v {
return []int{i, j}
}
}
}
return nil
}复杂度分析：
- 时间复杂度：两层循环，所以时间复杂度为
- 空间复杂度：没有使用额外空间，所以空间复杂度
方法二：暴力方法的排序优化
如果是已经排序的数组，在第二层循环，我们可以根据 与target的关系，每次排除一半的数据量。即，先将数据排序(时间复杂度),然后依次循环查找。第一层循环不变，第二层循环可折半来判断与target的关系
代码：略。有兴趣的朋友可以自行尝试
复杂度分析：
- 时间复杂度:
- 空间复杂度：
方法三：哈希表
注意到方法一中，我们一直在对比target – v与其他各个nums[j]，这部分时间复杂度有点高。因此，我们可以将target – v 存储起来，建立索引，使用哈希表，就可以在O(1)的时间复杂度内寻找 target – v。
这样，我们可以创建一个哈希表，对于每一个v，我们可以先查找target-v是否在哈希表中，如果在，那么说明我们找到了；否则，我们就将v插入到哈希表中。
代码如下：
//golang
// 例如 nums = [2,7,11,15], target = 9
// 1.初始化hashTable为空。开始遍历数组。首先nums[0]为2，它所需要的数为9-2=7，
// 查找hashTable发现没有7，那么将2:0插入到hashTable中，此时hashTable={2:0}
// 2. 继续遍历数组，得到nums[1]为7，所需要的数为9-7=2，查找hashTable发现里面有2
// 那么找到了所需要的数对，返回7的下标--1，以及hashTable[2]--0 结束函数。
func twoSum(nums []int, target int) []int {
//创建一个哈希表，来存储target -v
//哈希表的key: nums[i];
//哈希表的value: 对应nums[]的下标
hashTable := map[int]int{}
for i, v := range nums { //遍历数组
if res, ok := hashTable[target - v]; ok { //如果哈希表中存在key的值同遍历的v的和是target，说明找到了
return []int{res, i}
}
//如果不是，那么插入到哈希表中
hashTalbe[v] = i
}
return nil
}复杂度分析：
- 时间复杂度：一层循环，循环里面的是O(1)，所以复杂度为O(N)
- 空间复杂度：hashTable存储，最大开销为O(N).