【算法】两数之和
程序员文章站
2022-07-14 15:24:26
...
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1 暴力**
let nums = [2, 7, 11, 15];
let tarhet = 9;
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length ; i++){
let temp = target - nums[i];
for(let j = i + 1 ; j < nums.length ; j++){
if(temp === nums[j]){
return [i,j];
}
}
}
};
nums = [3,2,4]
tarhet = 6;
let start = new Date();
let t = twoSum(nums,tarhet);
let end = new Date();
console.log(end - start);
console.log(t);
复杂度分析
1、时间复杂度: O(n²)
2、空间复杂度:O(1)
两遍哈希表
var twoSum2 = function(nums, target) {
const m = new Map();
for(let i = 0; i < nums.length ; i++){
m.set(nums[i],i);
}
for(let j = 0 ; j < nums.length ; j++){
let temp = target - nums[j];
// console.log(m,m.get(temp));
if(m.has(temp) && m.get(temp) !== j){
return [j,m.get(temp)]
}
}
};
start = new Date();
t = twoSum2(nums,tarhet);
end = new Date();
console.log(end - start);
console.log(t);
一遍哈希表
这是一种非常巧妙的思路。
1、先计算差值
2、寻找差值
3、保存当前值到Hash中
这样做,巧妙的利用了一个值不能被使用两次:
1、避免了同一个值被两次使用。
2、避免了不必要的遍历
return 的值也是很有意思,因为是减法,要把i
放在数组的后一位
var twoSum3 = function(nums, target) {
const m = new Map();
for(let i = 0; i < nums.length ; i++){
let temp = target - nums[i];
if(m.has(temp)){
return [m.get(temp),i]
}
m.set(nums[i],i);
}
}
start = new Date();
t = twoSum3(nums,tarhet);
end = new Date();
console.log(end - start);
console.log(t);
下一篇: MySQL入门:用户设置 添加新用户