167.两数之和II-输入有效数组

题目

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1和index2。

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

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

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

示例 2：

    输入：numbers = [2,3,4], target = 6
    输出：[1,3]
    解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

    输入：numbers = [-1,0], target = -1
    输出：[1,2]
    解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 非递减顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

想法

拿到这个编程题，最开始的想法是可以双重循环然后比对，这样就可以实现，提交代码之后发现超时了。功能可以满足，但是时间复杂度为O (n^2)不满足

双循环

var twoSum = function(numbers, target) {
    for(let i = 0; i < numbers.length; i ++){
      for(let j = i + 1; j < numbers.length; j ++){
        if(numbers[i] + numbers[j] == target){
            return [i+1,j+1]
        }
      }
    }
};

new Map

后来又觉得是不是可以用Map结构的来存储，也只需要一次循环

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let map = new Map();
    for(let i = 0; i < numbers.length; i ++){
        let result = target - numbers[i];
        if(map.has(result)){
            return [map.get(result)+1, i+ 1]
        }
        map.set(numbers[i],i)
    }
};

双指针

这个是看题解发现的一个新思路，因为这是一个排序的数据

所以可以头尾指针向中间靠拢，

numbers：2 6 9 10
---------------L(2)---R(10)
target： 11

当第一个和最后一个如果相加 大于 结果，比如 2 + 10 大于 11 ，而这个又是排序的，
如果是 L 前进一步就是6 +10 大于 11 ，比刚刚还大，只能是 R 向后退一步，2 + 9 正好 等于 11

得出结论就是
当两个值 大于 结果时，尾指针需要后退；
当两个值 小于 结果时，头指针需要向前；

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let l = 0, r = numbers.length - 1;
    while(l < r){
        if(numbers[l] + numbers[r] < target){
            l ++;
        }else if(numbers[l] + numbers[r] > target){
            r --;
        }else{
            return [l + 1, r + 1]
        }
    }
};

时间O(n) 空间O(1)
头尾指针的运行时间更少