Two Sum II - Input array is sorted

Given an array of integers that is alreadysorted in ascending 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.

Note:

• 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.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2

Analysis

这一题完全可以用Two Sum中的解法来做，但是因为这里输入是排序过的数组，可以用更高效的算法。

Loop with Binary Search

O(nlogn) time, O(1) space

Two Pointers

O(n) time, O(1) space

即用numbers[low] + numbers[high]和target比较大小，来决定是low向右移，还是high向左移动。

Solution

Binary Search - (3ms, 25.38%)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
         if (numbers == null || numbers.length == 0) {
             return new int[]{-1, -1};
         }
        int[] ans = new int[2];
        for (int i = 0; i < numbers.length; i++) {
            int idx = binarySearch(numbers, target - numbers[i], i + 1, numbers.length - 1);
            if (idx > 0) {
                ans[0] = i + 1;
                ans[1] = idx + 1;
                return ans;
            }
        }
        return ans;
    }
    private int binarySearch(int[] nums, int target, int left, int right) {
         if (nums == null || nums.length == 0) {
             return -1;
         }
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            } else if (target > nums[mid]) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {
            return left;
        } else if (nums[right] == target) {
            return right;
        }
        return -1;
    }
}

Two Pointers - (1ms, 76.02%)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;

        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target)
                return new int[]{low + 1, high + 1};
            else if (sum < target)
                ++low;
            else
                --high;
        }
        return new int[]{-1, -1};
    }
}