[lintcode medium] Two sum

numbers=[2, 7, 11, 15], target=9

return [1, 2]

You may assume that each input would have exactly one solution

Either of the following solutions are acceptable:

• O(n) Space, O(nlogn) Time
• O(n) Space, O(n) Time

public class Solution {
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum(int[] numbers, int target) {
        // write your code here
       
        int[] result=new int[2];
       
        if(numbers==null || numbers.length==0) return result;

        int n=numbers.length;
       
        for(int i=0;i<n;i++)
        {
            int left=n-1;
            while(left>i)
            {
              int sum=numbers[i]+numbers[left];
              if(sum==target)
              {
                 result[0]=i+1;
                 result[1]=left+1;
                 return result;
              }
              else
              {
                  left--;
              }
            }
        }
       
        return result;
    }
}