Monday, December 22, 2014

Two Sum with sorted and unsorted input array

The first problem provides and unsorted array and requires to output indices. This one is actually a little bit more complicated than with a sorted one, and require extra O(n) space.

With unsorted array


Given an array of integers, 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.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
public class FindSum {
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length < 2)
            throw new Error ("Null array or insufficient length");
        HashMap hm = new HashMap ();
        for (int i = 0; i < numbers.length; i++)
            hm.put(numbers[i], i + 1);
        int[] rst = new int[2];
        rst[0] = -1;
        rst[1] = -1;
        for (int i = 0; i < numbers.length; i++)
        {
            if (!hm.containsKey(target - numbers[i]))
                continue;
            int index1 = hm.get(target - numbers[i]);
            if (index1 == i + 1)
                continue;
            rst[0] = i + 1;
            rst[1] = index1;
            return rst;
        }
        return rst;
        
    }
}

With sorted array



public class TwoSum {
 public int[] twoSum(int[] numbers, int target)
 {
  if (numbers == null || numbers.length < 2)
   throw new Error("Null array or insufficient length");
  int start = 0;
  int end = numbers.length - 1;
  int[] rst = new int[2];
  rst[0] = -1;
  rst[1] = -1;
  while (start < end)
  {
   int sum = numbers[start] + numbers[end];
   if (sum == target)
   {
    rst[0] = start;
    rst[1] = end;
    return rst;
   }
   else if (sum < target)
    start++;
   else
    end--;
  }
  return rst;
   
 }

}

No comments:

Post a Comment