LeetCode 题解:1. 两数之和,Map+ 队列 + 双指针,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 09 月 14 日
LeetCode题解:1. 两数之和,Map+队列+双指针,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/two-sum/



解题思路:



  1. 使用Map缓存当前数组的值对应的index,需要注意的是,数组的值有可能相同。也就是说同一个值可能对应多个index,因此选择用队列存储index。再将队列存储在Map中。

  2. 将数组排序,使双指针能够根据计算结果选择方向推进。

  3. 用双指针向中间推进,如果遇到两数字和等于target,则根据当前的值从队列中取出index,并返回结果。



/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
// 使用Map缓存数组value与index的关系
let map = new Map();
// 由于value的值可能重复,因此选用队列存储index
nums.forEach((value, index) => {
if (map.get(value)) {
map.get(value).push(index);
} else {
map.set(value, [index]);
}
});
// 将数组排序,之后可以根据两数字和与target的大小关系,判断指针的移动方向
nums.sort((a, b) => a - b);
// 定义双指针,分别在数组的头尾
let i = 0;
let j = nums.length - 1;
// 双指针想中间移动
while (i < j) {
// 计算当前指针对应的两数字和
let sum = nums[i] + nums[j];
// 如果sum小于target,表示左指针需要向右移动
if (sum < target) {
i++;
} else if (sum > target) {
// 如果sum大于target,表示左指针需要向左移动
j--;
} else {
// 如果遇到sum等于target,则从队列中取出index,并返回结果
return [map.get(nums[i]).shift(), map.get(nums[j]).shift()];
}
}
};



发布于: 2020 年 09 月 14 日 阅读数: 19
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:1. 两数之和,Map+队列+双指针,JavaScript,详细注释