LeetCode 1 两数之和

给定一个整数数组 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).