leetcode 1. 两数之和

https://leetcode-cn.com/problems/two-sum/

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

提示

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

解一：哈希法

思路

遍历数组，扫描到数字a时，计算b=target-a

• 如果b在哈希表中，直接返回结果
• 否则，将a存入哈希表，继续遍历

语法

ES6 new Map()
Map字典是以[键，值]的形式存储
set()
设置键名key对应的键值为value，然后返回整个 Map 结构

get()
get方法读取key对应的键值，如果找不到key，返回undefined

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len=nums.length;
    //新建Map对象
    let sumMap=new Map();
    //0号元素在它之前一定没有元素与之匹配，所以先存入哈希表
    sumMap.set(nums[0],0);
    //从1号元素开始遍历
    for(let i=1;i<len;i++){
        match=target-nums[i];
        //如果match在Map中，即找到目标数对
        //返回Map中存储的数对应的索引和当前索引
        if(sumMap.get(match)!==undefined){
            return [sumMap.get(match),i];
        }
        //否则，即match不在Map中
        //将它的值和索引存入Map，方便之和根据值查索引
        sumMap.set(nums[i],i);
    }
};

复杂度分析

空间换时间
哈希时间复杂度$O(1)$，遍历n次
时间复杂度$O(N)$，空间复杂度$O(N)$