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

题目链接
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

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

也就是说在一个数组里面找到 arr[i] + arr[j] == target 并且 i < j
那么很简单的,我们就会想到扫描

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i=0;i<numbers.length ;i++){
            for(int j=i;j<numbers.length;j++){
                if(numbers[i] + numbers[j] == target && i!=j){
                    return new int[]{i+1 ,j+1};
                }
            }
        }
        return new int[]{-1,-1};

    }
}

执行用时：305 ms, 在所有 Java 提交中击败了5.05%的用户
内存消耗：40.3 MB, 在所有 Java 提交中击败了6.67%的用户

费时费力,有没有简单的方法呢?考虑到数组已经排序, 所以想到双指针,一个在数组头,一个在数组尾 , 如果相加起来 < target , 那就向右移动头指针, 反之亦然

那么理所当然的, 有这样的代码

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int tail = numbers.length - 1;
        int head = 0;
        while(head < tail){
            if(numbers[head] + numbers[tail] == target){
                return new int[]{head+1 , tail+1};
            }else if(numbers[head] + numbers[tail] > target){
                tail --;
            }else{
                head++;
            }
        }
        return new int[]{-1,-1};
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了95.52%的用户
内存消耗：40.3 MB, 在所有 Java 提交中击败了6.67%的用户

可见耗时确实减少了,还能不能更快? 能! 考虑到数组已经排过序 , 那么右面的尾指针没有必要放到数组最后 , 可以稍微计算一下 , 例如

arr[] = [1,2,3,4,5,6,7,8,9,100,200,300,400,500,600, ....];
target = 3

情如上面的情况, 我们没有必要把尾指针放在数组最后, 还可以再优化, 所以就有了下面的代码

class Solution {
    public int[] twoSum(int[] arr, int target) {
        int left = 0;
        int right = binarySerachForRightPosition(arr, target - arr[0]);
        while (left < right) {
            if (target == arr[left] + arr[right])
                return new int [] {++left, ++right};
            else if (target < arr[left] + arr[right])
                right --;
            else
                left ++;
        }
        return new int [] { -1, -1};

    }
    private int binarySerachForRightPosition(int [] arr, int target) {
        int left = 1, right = arr.length - 1;
        for (int mid = left + ((right - left) >> 1); left <= right; mid = left + ((right - left) >> 1)) {
            if (target == arr[mid])
                return mid;
            else if (target < arr[mid])
                right = mid - 1;
            else
                left = mid + 1;
        }
        return left - 1;//important, left is where we can insert the target into the array and maintain the array is not descending,
    }
}

说干就干

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.9 MB, 在所有 Java 提交中击败了6.67%的用户

起飞! 我直接起飞!