亲宝软件园·资讯

展开

leetcode-0001 两数之和

郭励之 人气:0

题目地址:https://leetcode-cn.com/problems/two-sum/

1.暴力解法

直接双重循环,枚举出所有可能的解,时间复杂度为O(n^2),空间复杂度为O(1)

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

2.HashTable

  • 第一次循环将数组nums中的每个数都放入map中
  • 第二次循环判断target - nums[i]是否在map中

时间复杂度O(n), 空间复杂度O(1)

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

  throw new Error('没有这样两个数')
}

3.HashTable优化版

一次循环,先检查map中是否含有target - nums[i],如果找到了,那就是我们要的结果;如果没有找到就将这个nums[i]存入map中,继续进行下一次循环,此种解法由于只循环了一次,因此时间复杂度会优于解法2

时间复杂度O(n),空间复杂度O(n)

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

  throw new Error('没有这样的两个数')
};

更多leetcode题解和数据结构方面的知识,请关注我的github:https://github.com/GuoLizhi/

加载全部内容

相关教程
猜你喜欢
用户评论