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

二分查找法

class Solution {
    public int[] twoSum(int[] numbers, int target) {

        int[] res = new int[2];

        /**
         * 对于每一个元素，在后面的子数组中寻找是否有匹配的元素
         * 因为数组是有序的，使用二分查找法寻找更快
         * 该数组索引是从1开始的，最终返回值要加1
         */
        for (int i = 0; i < numbers.length - 1; i++) {

            int index = binarySearch(numbers, i + 1, numbers.length - 1, target - numbers[i]);

            if (index != -1){

                res[0] = i + 1;
                res[1] = index + 1;
                break;
            };
        }

        return res;
    }

    public int binarySearch(int[] arr, int left, int right, int value){

        if (left > right){
            return -1;
        }

        int mid = left + (right - left) / 2;

        if (arr[mid] == value){
            return mid;
        }
        else if (arr[mid] < value){
            return binarySearch(arr, mid + 1, right, value);
        }
        else {
            return binarySearch(arr, left, mid - 1, value);
        }
    }
}

/**
 * 时间复杂度 O(nlogn)
 * 空间复杂度 O(1)
 */

优化1——双指针法

class Solution {
    public int[] twoSum(int[] numbers, int target) {

        /**
         * 双指针遍历数组
         * 最大值和最小值相加，如果和大与目标值，右指针左移，反之左指针右移
         */
        int i = 0;
        int j = numbers.length - 1;
        int[] res = new int[2];

        while (i < j){

            if (numbers[i] + numbers[j] == target){

                res[0] = i + 1;
                res[1] = j + 1;
                break;
            }
            else if (numbers[i] + numbers[j] > target){
                j--;
            }
            else {
                i++;
            }
        }

        return res;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

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