Two Sum

Given an array of N distinct integers, write a program to find if there exists any pair of integers whose sum is x. This is popularly addressed as 2-SUM problem.

O(n^2) approach: Time complexity in worst case: O(n^2).

public static int[] twoSum(int[] numbers, int target) {
 int[] ret = new int[2];
 for (int i = 0; i < numbers.length; i++) {
  for (int j = i + 1; j < numbers.length; j++) {
   if (numbers[i] + numbers[j] == target) {
    ret[0] = i + 1;
    ret[1] = j + 1;
   }
  }
 }
 return ret;
}

HashMap version, Time complexity: O(n)

public int[] twoSum(int[] numbers, int target) {

        int a[] = new int[2];
        Hashtable<Integer, Integer> nums = new Hashtable<>();
        for(int i = 0;i < numbers.length;i++){
            Integer n = nums.get(numbers[i]);

            if (n==null) nums.put(numbers[i], i); //subtract array element from target number
            n = nums.get(target-numbers[i]); 
            if (n!=null && n<i)
            {//if such number exists in the table return the indicies
                a[0]=n+1;
                a[1]=i+1;
                return a;
            }
        }//end for loop
     return a;