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

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

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1和 index2，其中 index1必须小于 index2。

说明:

• 返回的下标值（index1和 index2）不是从零开始的。
• 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例1 ：

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题首先想到就应该是双指针法，思路也很简单，就是一个指针指向开头，另一个指针指向结尾，然后判断指针所指向的两数之和是否等于target，如果相等就返回相应的index；如果不等判断两数之和和target的大小，如果和大于target，则需要index2向左移动以此来缩小和，如果和小于target，则需要index1向右移动以此来增大和。

具体代码如下：

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        //这里用right = nums.length，下面的while循环条件就用left < right
        //这里如果是right = nums.length - 1，下面的循环条件就是left <= right
        //这是因为使用right = nums.length循环判等的话会出现越界
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;    //防止left和right太大导致相加除二溢出
            if (nums[mid] == target) {  //如果target就是nums[mid]的值的话就直接返回
                return mid;
            }
            if (target > nums[mid]) {   //如果target比nums[mid]大，我们向右子区间收缩，所以这里需要left = mid + 1
                left = mid + 1;
            }
            if (target < nums[mid]) {
                //因为我们上面的right = nums.length，并且循环条件为left < right
                //所以这里不能使用right = mid - 1，具体的大家可以debug观察结果
                right = mid;
            }
        }
        return left;
    }
}

官方提示中还提到了二分查找，由于二分查找不能同时进行两个数的查找，我们最先能想到的就是固定一个数，然后去剩下的元素中找，看能不能找到一个值和target - numbers[i]的值相等，如果能，则返回两者索引，如果不能，则返回-1。

具体代码如下：

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int right = numbers.length - 1;
        //固定一个值，在剩下的元素中找一个数是否等于target - numbers[i]的值
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] + numbers[right] == target) {
                return new int[]{i + 1, right + 1};
            }
            int index2 = binarySearch(numbers, i + 1, right, target - numbers[i]);
            if (index2 != -1) {
                return new int[]{i + 1, index2 + 1};
            }
        }
        return new int[]{-1, -1};
    }


    //手写binarySearch()方法，当然也可以直接调用Arrays.binarySearch()方法
    public int binarySearch(int[] nums, int fromIndex, int toIndex, int target) {
        int left = fromIndex;
        int right = toIndex - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return -1;
    }
}