首页
两数之和

leetcode:两数之和

描述:

image-20210221214935645

题解:

思路一:暴力循环法

暴力循环法的思路很简单,也比较符合大家的惯性思维。双层数组遍历,外层循环遍历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)
  }
}