两数之和

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

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

示例:

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

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

解题思路:

  • 初始化一个 map = new Map()
  • 从第一个元素开始遍历 nums
  • 获取目标值与 nums[i] 的差值,即 k = target - nums[i] ,判断差值在 map 中是否存在
    • 不存在( map.has(k)false ) ,则将 nums[i] 加入到 map 中(key为nums[i], value为 i ,方便查找map中是否存在某值,并可以通过 get 方法直接拿到下标)
    • 存在( map.has(k) ),返回 [map.get(k), i] ,求解结束
  • 遍历结束,则 nums 中没有符合条件的两个数,返回 []

时间复杂度:O(n)

代码实现:

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