两数之和

第 13 天

​两数之和​

难度:简单

题目

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

输入:nums = [3,3], target = 6
输出:[0,1]

题解

思路一:双循环

第一次接触题目,首先肯定是想到暴力解法,通过双循环遍历数组;

注意用 indexof 也是一种循环方式。

var twoSum = function(nums, target) {
for(let i = 0, len = nums.length;i < len;i++){
// 因为同一元素不允许重复出现,所以从i的下一位开始遍历
for(let j = i + 1;j < len;j++) {
if(nums[i] + nums[j] === target) {
return [i, j];
}
}
}
// 所有样例都是有返回结果的,这里无所谓
return [-1, -1];
};

思路二:用 map

方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此,我们需要一种更优秀的方法,能够快速寻找数组中是否存在目标元素。如果存在,我们需要找出它的索引。

使用哈希表,可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

对象写法:

var twoSum = function(nums, target) {
//创建空对象obj
const obj = {}
// 拿到nums的长度
const len = nums.length
// 遍历数组
for(let i=0;i<len;i++){
// 可以把target-数组元素的值作为obj的键,不存在则存储,存在就返回键和i
if(obj[target - nums[i]] !== undefined){
return [obj[target - nums[i]],i]
}
//不存在则将nums[i]的值作为键,i为值
obj[nums[i]] = i
}
};

Map 写法:

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

总结

很多题用双循环解题都可以转化为 map,减少一层循环的复杂度。

发表评论

相关文章