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

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

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

思路

二分法

• 从 numbers 取出一个元素 numbers[i]，在 numbers 中 i 之后的元素中查找 target - numbers[i]
• 查找到之间返回，不然依次从 numbers 中取后面一个元素

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

双指针

1. 从二分法查找中会发现，其实不用查找完二分的节点就已经知道当前这个 i是否能满足要求
2. 那当知道这个i不在满足要求时就没有必要接着二分了，直接切换i就可以
3. 那left 和right就成立两个动态的索引指针了

var twoSum = function(numbers, target) {
    let left=0,right=numbers.length-1
    while(left<=right) {
        if(numbers[left]+numbers[right] === target) {
            return [left+1, right+1]
        } else if(numbers[left] + numbers[right] > target) {
            // 当和大于target，则右侧减小(较大的值减小)
            right--
        } else {
            left++
        }
    }
};