167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted 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. 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

Solution:

Since the input is sorted, we can apply two pointers to find the answer.

One pointer points to the start of the array and the other points to the end of the array.

If the sum of the numbers pointed by these two points equals to target, we find the answer.

If the sum is smaller than target, we advance the first pointer.

Otherwise we decrease the second one.

The time complexity is O(n) and the space complexity is O(1).



Code:

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