A-A+

LeetCode–两数之和

2020年10月12日 全部, 技术 暂无评论 阅读 292 次浏览 次

题目描述:

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题:

1.枚举

var twoSum = function(nums, target) {
  let arr = [],
    len = nums.length

  for(let i = 0; i < len - 1; i++){
    for(let j = i+1; j< len; j++){
      if((nums[i] + nums[j]) == target){
        arr.push(i,j)
      }
    }
  }
  return arr
};

缺点:1.双重循环则时间复杂度 为O(N²)

2. Map 或者 对象({})

减少查询时间,通过key,val模式快速定位将时间复杂度降到 O(1),但是这题时间复杂度可以为O(N)

let twoSum = function(nums, target){
  let len = nums.length,
    numMap = new Map()

  for(let i = 0; i < len;i++){
    if(numMap.has(target - nums[i])){
      return [numMap.get(target - nums[i]),i]
    }
    numMap.set(nums[i],i)
  }
}

同样空间复杂度提高到了O(N),通过空间换时间。

标签:

给我留言

Copyright © 前端黑板报 保留所有权利.   Theme  Ality 沪ICP备18002623号-2

用户登录