leetcode上面的题目:

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

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路:new Map()建立一个哈希表,使用 .set()方法为Map对象添加指定了keyvalue的键值对,再利用for循环,在循环中,使用目标值依次减去数组中的每个数,得到一个结果,如果该结果在哈希表中并且下标不是当前循环中的数字(防止 6 = 3+3,8=4+4等情况);

具体方法:(使用TS编写)

/**
 * @description: 两数之和
 * @param {Array} nums 传入的数组
 * @param {Number} target 目标值
 * @return {Array} 符合条件的脚标 
 */
const twoSum = (nums: number[], target: number): number[] => {
  const _length = nums.length; //获取传入数组的长度
  let _hash = new Map();  //使用new Map定义哈希表

  //初始化哈希表
  for(let i = 0; i < _length; i++){
    _hash.set(nums[i], i);
  }

  //循环比对
  for(let i = 0; i < _length; i++){
    let _resNum = target - nums[i];

    if(_hash.has(_resNum) && i !== _hash.get(_resNum)){
      return [i, _hash.get(_resNum)];
    }
  }
};

如果采用最原始的方式,循环嵌套比对,时间复杂度会是O(n2)

使用Map结构,时间复杂度是O(n)

还有一种一遍哈希法,如果拿到一个数字,先在哈希表中查找是否有配对的数字,如果有,则返回两个数字,如果没有,那就继续存入哈希表,理论上来讲效率更高:

/**
 * @description: 两数之和
 * @param {Array} nums 传入的数组
 * @param {Number} target 目标值
 * @return {Array} 符合条件的脚标 
 */
const twoSum = (nums: number[], target: number): number[] => {
  const _length = nums.length; //获取传入数组的长度
  let _hash = new Map();  //使用new Map定义哈希表

  //循环比对
  for(let i = 0; i < _length; i++){
    let _resNum = target - nums[i];

    if(_hash.has(_resNum)){
      return [_hash.get(_resNum), i];
    }

    _hash.set(nums[i], i);

  }
};

可以从下图看出,使用暴力循环,时间比哈希法长很多: