算法题：167. 两数之和 II - 输入有序数组

题

思路

这题跟《算法题：1. 两数之和》很像，而且那题的解法也可以用于解答这题。不过由于这题的数组是排好序的，所以有更优解。

双指针

function twoSum(numbers: number[], target: number): number[] {
    let left = 0;
    let right = numbers.length - 1;
    while(left < right){
        const sum = numbers[left] + numbers[right];
        if(sum === target){
            return [left + 1, right + 1];
        } else if(sum < target){
            left++;
        } else {
            right--;
        }

    }
    return [];
};

二分查找

function twoSum(numbers: number[], target: number): number[] {
    let left = 0;
    let right = 0;
    let mid = 0;
    let sum = 0;
    for(let i = 0; i < numbers.length; i++) {
        left = i + 1;
        right = numbers.length - 1;
    
        while(left <= right){
            mid = ~~((right - left) / 2) + left;
            sum = numbers[mid] + numbers[i];
            if(target === sum){
                return [i + 1, mid + 1];
            }
            if(sum > target){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
    }
    return [];
};

总结

从结果可以看出：除了暴力枚举外，其他几种解法性能相差不大。不过可能是测试用例不多，不然map和双指针的o(n)会比二分查找的n(nlogn)快，而且双指针又比map省空间才对。