Answer 1

思路一：暴力破解法

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

由于进行了双重循环，时间复杂度是O(n^2), 空间复杂度O(1)

思路二：两趟哈希表

function twoSum(nums, target) {
  const map = {}
  for (const [i, n] of nums.entries()) {
    map[n] = i
  }
  for (const [i, n] of nums.entries()) {
    let number = target - n
    if (number in map) {
      return [i, map[number]]
    }
  }
}

• 先用一个哈希表存储数组的值于对应数组下标，然后再遍历数组寻找结果
• 时间复杂度O(n), 空间复杂度O(n)

思路三：一趟哈希表

var twoSum = function(nums, target) {
  const map = {}
  for (let i = 0; i < nums.length; i++) {
    const n = nums[i]
    if (target - n in map) {
      return [map[target - n], i]
    } else {
      map[n] = i
    }
  }
}

• 在给哈希表添加元素的同时寻找有没有符合目标的答案，如果有就直接返回，没有就继续构造哈希表。
• 时间复杂度O(n), 空间复杂度O(n)

第二种思路可能有点问题，当数组内容都是重复的内容例如twoSum([2,2,2,2],4)