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

[chencl1986]

原题链接：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()];
    }
  }
};