2 TOW SUM Ⅱ

题目

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例:

输入: numbers = [2, 7, 11, 15], target = 9

输出: [1,2]

解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解答

一遍哈希表

感觉和1差不多，就是返回值得升一位。

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    alert("input type incorrect");
    return;
  }

  const arrMap = new Map()
  for (let i = 0; i < nums.length; i++) {
      const result = target - nums[i];
      if (arrMap.has(result)) {
        return [arrMap.get(result)+1, i+1]   // 这里返回值 +1
      }
      arrMap.set(nums[i], i)
  }
};

Runtime: 48 ms, faster than 98.63% of JavaScript online submissions for Two Sum II - Input array is sorted.

Memory Usage: 35.2 MB, less than 44.43% of JavaScript online submissions for Two Sum II - Input array is sorted.

双指针

因为已经排序好了，所以就从外向内验证。如果加起来小了，就把low加一位，如果大了就减一位。直到找到两个值。

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') return;

  let low = 0;
      high = nums.length - 1;

  while (low < high) {
    let sum = nums[low] + nums[high];
    if (sum < target) {
      low ++
    } else if (sum > target) {
      high --
    } else {
      return [low+1, high+1]
    }
  }
};

Runtime: 68 ms, faster than 38.61% of JavaScript online submissions for Two Sum II - Input array is sorted.

Memory Usage: 35.1 MB, less than 57.40% of JavaScript online submissions for Two Sum II - Input array is sorted.

两分法

双指针做了很多无用功。于是有用两分法来找目标值。

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    return;
  }

  for (let index = 0; index < nums.length; index++) {
    const aim = target - nums[index];
    let start = index + 1;
            end = nums.length - 1;
    while (start <= end) {
      let mid = Math.round((start + end) / 2)
      if (nums[mid] === aim) {
        return [index+1, mid+1]
      } else if (nums[mid] < aim) {
        start = mid + 1
      } else {
        end = mid - 1
      }
    }
  }
};

Runtime: 56 ms, faster than 88.04% of JavaScript online submissions for Two Sum II - Input array is sorted.

Memory Usage: 35.4 MB, less than 18.95% of JavaScript online submissions for Two Sum II - Input array is sorted.

哈希表 + 两分法

两分法曾经查过的地方，下一轮就没查了，因此想建立一个哈希表，来查询曾经查过的数据。

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    return;
  }

  const arrMap = new Map()
  for (let i = 0; i < nums.length; i++) {
    const aim = target - nums[i];
    if (arrMap.has(aim)) {
      return [i + 1, arrMap.get(aim) + 1]
    }

    let start = i + 1;
    end = nums.length - 1;
    while (start <= end) {
      let mid = Math.round((start + end) / 2)
      if (nums[mid] === aim) {
        return [i + 1, mid + 1]
      } else if (nums[mid] < aim) {
        start = mid + 1
      } else {
        end = mid - 1
      }
      arrMap.set(nums[mid], mid)
    }
  }
};

Runtime: 76 ms, faster than 31.73% of JavaScript online submissions for Two Sum II - Input array is sorted.

Memory Usage: 35.2 MB, less than 38.09% of JavaScript online submissions for Two Sum II - Input array is sorted.