leetcode：两数之和

描述：

题解：

思路一：暴力循环法

暴力循环法的思路很简单，也比较符合大家的惯性思维。双层数组遍历，外层循环遍历nums数组，内层循环判断数组余下的值是否存在相加等于target的元素

ES6

function twoSum(nums, target) {
  let i = 0, j;
  for (; i < nums.length; i++) {
    for (j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] == target) {
        return [i, j];
      }
    }
  }
}

时间复杂度：O(n^2)

思路二：两遍散列表

对于这种问题，在算法中首先想到的是用散列表来实现，把 O(n) 的问题转换成 O(1) 的问题来实现。在这里，我们只是使用散列表的思想，在Javascript里面没有散列表这种数据类型，我们可以使用 Map 来实现。

ES6

function twoSum(nums, target) {
  const map = new Map(nums.map((value, key) => [value, key]))
  let i = 0, complement;
  for (i; i < nums.length; i++) {
    complement = target - nums[i];
    if (map.has(complement) && map.get(complement) !== i) {
      return [i, map.get(complement)]
    }
  }
}

时间复杂度：O(n)

思路三：一遍散列表

在思路二的基础上做的优化。我们没必要一开始就对整个nums数组做一遍散列函数转换。在迭代nums数组的时候，我们把元素插入到Map的同时，会首先检查Map中是否已存在满足条件的目标元素。如果存在，直接返回结果；不存在，就插入到Map里面

ES6

function twoSum(nums, target) {
  const map = new Map()
  let i = 0, complement
  for (i; i < nums.length; i++) {
    complement = target - nums[i]
    if (map.has(complement)) {
      return [map.get(complement), i]
    }
    map.set(nums[i], i)
  }
}