题干

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

解法一：选择排序思想

其实这种想法不仅可以用于有序的排列，也可以用于无序的集合。

执行用时:312 ms, 在所有 JavaScript 提交中击败了11.29%的用户

内存消耗:38 MB, 在所有 JavaScript 提交中击败了92.21%的用户

很明显的得出使用选择排序这种方式时间复杂度并不高。

  var twoSum = function (numbers, target) {
    let targetarray = []
    for (let index = 0; index < numbers.length; index++) {
      let pretarget = numbers[index]//记录当前第一层循环的值
      for (let indey = index+1; indey < numbers.length; indey++) {
        if (pretarget + numbers[indey] == target) {
          targetarray[0] = index + 1;
          targetarray[1] = indey + 1;
          return targetarray;
        }
      }
    }
    return targetarray
  };
复制代码

解法二：双指针

执行用时：84 ms, 在所有 JavaScript 提交中击败了75.78%的用户

内存消耗：38.2 MB, 在所有 JavaScript 提交中击败了61.36%的用户

使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

• 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
• 如果 sum > target，移动较大的元素，使 sum 变小一些；
• 如果 sum < target，移动较小的元素，使 sum 变大一些。

  var twoSum2 = function (numbers, target) {
    let first = 0, end = numbers.length - 1;
    let targetArr=[];
    while (first < end) {
        let tempnum = numbers[first] + numbers[end];
        // 如果时升序则反之
        if (tempnum > target) {
            end -= 1;
        } else if (tempnum < target) {
            first += 1;
        } else if (tempnum == target) {
            targetArr.push(first+1)
            targetArr.push(end+1)
            return targetArr;
        }
    }
    return targetArr
};
复制代码