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

Similar question: Two Sum

Solution 

It is easier than Two sum, because it is sorted. We can use two pointers and a little bit greedy to find the two elements in O(n) time without extra space.

Idea, pointer i =0, pointer j= last Index, so num[i] is the smallest and num[j] is the biggest number in the array. Increase i when num[i]+num[j]< target because we can't find any j that can increase the sum to get the target and we can safely discard num[i]. Same idea to decrease j when num[i]+ num[j] > target. The invariant of the iteration is that num[i] is always the smallest number among all unvisited numbers and num[j] is always the largest number among all unvisited numbers. 

   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) j--;  
       else if(numbers[i]+numbers[j]<target) i++;  
       else{  
         res[0]=i+1;  
         res[1]=j+1;  
         return res;  
       }  
     }  
     return res;  
   }