欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法】两数之和

程序员文章站 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);
相关标签: 算法 两数之和