【算法】两数之和-蒲公英云

【算法】两数之和

小鱼儿 2022-05-16 12:08 275阅读 0赞

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 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);