【leetcode】1. 两数之和
文章目录
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
实现思路:
题目常规解法是 O(n^2) 的暴力解,分析可以发现,利用好 hashMap 就可以用空间换取时间,把时间复杂度降为 O(n)
我的实现:
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new HashMap()
const numsLen = nums.length
for (let i = 0; i < numsLen; i++) {
const cup = target - nums[i]
const index = map.find(cup)
if (index !== -1) return [index, i]
else map.put(nums[i], i)
}
};
class HashMap {
constructor () {
this.map = {}
}
put (key, value) {
this.map[key] = value
}
find (key) {
return key in this.map ? this.map[key] : -1
}
}
成绩


评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论