两数之和II-输入有序数组

二 题目

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

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

说明:

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

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {

};

根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。

三 解题思路

两种解法：

• 暴力破解
• 哈希表
• 双指针

暴力破解

const twoSum = (numbers, target) => {
  for (let i = 0; i < numbers.length; i++) {
    const index = numbers.indexOf(target - numbers[i], i + 1);
    if (index > -1) {
      return [i + 1, index + 1];
    }
  }
};

哈希表

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

双指针

const twoSum = (numbers, target) => {
  let low = 0, high = numbers.length - 1;
  while (low < high) {
    const sum = numbers[low] + numbers[high];
    if (sum === target) {
      return [low + 1, high + 1];
    } else if (sum < target) {
      low++;
    } else if (sum > target) {
      high--;
    }
  }
};

除此之外，官方题解还有二分查找，这里就不哆嗦了~

四 统计分析

本题不需要统计分析。

五 套路分析

本题暂未发现任何套路，如果有但是 jsliang 后面发现了的话，会在 GitHub 进行补充。

jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。