【LeetCode 0167】【数组】两数之和(2)

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

题解

• 二分查找O(nlog)：有序自然想到二分查找，从左往右迭代数组每个元素num，在后面剩下的数组元素中二分查找到target-num

var twoSum = function(numbers, target) {
    const binarySearch = (numbers,key,i)=>{
        let [start,end] = [i,numbers.length-1]
        while(start <= end){
            let mid = (start + end) >>> 1
            if(numbers[mid] < key){
                start  = mid + 1;
            }else if(numbers[mid]> key){
                end = mid - 1;
            }else{
                return mid + 1 // 返回第几个，而不是索引
            }
        }
        return -1;
    }
    for(let i = 1 ; i <= numbers.length ; i++){ // i 从1 开始
        let another = binarySearch(numbers,target - numbers[i-1],i);
        if(another != -1){ // 找到另一个数字，返回
            return [i,another]
        }
    }
    return [0,0]
};

• 双指针O(n)， 当双指针所指数字之和小于目标值，左指针右移动；反之右指针左移

var twoSum = function(numbers, target) {
    let [left,right] =[0, numbers.length - 1];
    while (left < right) {
        if (numbers[left] + numbers[right] > target) {
        	// 两数之和偏大，右指针左移
            right--;
        } else if (numbers[left] + numbers[right]  < target) {
            // 两数之和偏小，左指针右移
            left++;
        } else { //找到两数，返回
            return [left + 1, right + 1];
        } 
    }
};