TwoSumII_InputArrayIsSortedOPT [source code]

public class TwoSumII_InputArrayIsSortedOPT {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int i = 0;
        int j = numbers.length - 1;
        int mid = 0;
        while (i < j) {
            mid = i + (j - i)/2;
            if (numbers[mid] > target) {
                j = mid;
            } else if (numbers[mid] < target) {
                i = mid + 1;
            } else {
                break;
            }
        }

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

这个是 submission 最优解, 0ms;
这个算法的核心优化就是在搜索之前加了一个binary search, 从而让整个算法的速度做到了 sublinear;

这里是利用了binary search的一些性质: 如果被搜索的数不在 array 里面, 那么最后返回的时候, 首先肯定有
i == j, 然后 i 这个位置的这个数一定是the successor in the array, 也就是将将大于target 的数, the smallest
number in the array that is larger than target;

比如2, 7, 11, 15里面 target 是9的这个例子, 那么能够加出来9的, 肯定不可能大于9, 所以只要找到9的 successor, 然后
在此之前找就行了;

注意的是如果numbers 里面包含9, 其实也不影响, 比如numbers 是: 2,7,9,11,15, 最后就是在2,7,9里面找, 其实这个还是
可以成功的;

Problem Description

Given an array of integers that is already sorted in asctailing order, find two numbers such that
they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target,
where index1 must be less than index2. Please note that your returned answers (both index1 and
index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same
element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Difficulty:Easy
Category:Algorithms
Acceptance:47.14%
Contributor: LeetCode
Topics:
Array Two Pointers Binary Search
You might like:
(E) Two Sum
Company:
Amazon