167. Two Sum II - Input array is sorted (https://leetcode.com/problems/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, wher…

167. Two Sum II - Input array is sorted (#1 Two Pointers).java

// Two pointer solution: begin/end pointer
// Time: O(n), 1ms
// Space: O(1), 37.9mb
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        
        while(left < right) {
            if(numbers[left] + numbers[right] == target) {
                return new int[]{left + 1, right + 1};
                
            } else if(numbers[left] + numbers[right] < target) {
                // If sum is smaller, move left pointer rightward to make it larger
                left++;
                
            } else {// numbers[left] + numbers[right] > target
                right--;
            }
        }
        
        return new int[]{-1, -1};
    }
}

167. Two Sum II - Input array is sorted (#2 Binary Search).java

//0ms solution, faster than #1 Two Pointers
class Solution {
  public int[] twoSum(int[] numbers, int target) {
        boolean isBegin = true;
        int [] result = new int [2];
        int temp = 0, before = 0, end = numbers.length, index = 0;
        while(before<end){
            if(isBegin){
                temp = target - numbers[before];
                index = Arrays.binarySearch(numbers, before, end, temp);//Find index2 or the first element larger than temp
                if(index > 0){
                    result[0] = before + 1;
                    result[1] = index + 1;
                    return result;
                }else{
                    end = -index - 1 - 1;  //index2 can't be greater than the first element before insert position
                    isBegin = false;
                }
            }else{
                temp = target - numbers[end];
                index = Arrays.binarySearch(numbers, before, end, temp);//Find index1 or the first element larger than temp
                if(index > 0){
                    result[0] = index + 1;
                    result[1] = end + 1;
                    return result;
                }else{
                    before = -index - 1;  //index1 can't be smaller than the first element after insert position
                    isBegin = true;
                }
            }
        }
    return result;
    }
}