Two Sum

Posted on

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
public static int[] twoSum(int[] nums, int target) {
    if (nums == null) {return null;}

    /* the size of the result int[] is fixed: 2. Because assumed only one group of solution */
    int[] result = new int[2];

    /* HashMap: key is the element, value is the index of the element in array nums */
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; i++) {
       if (map.containsKey(target - nums[i])) {
          result[1] = i;
          result[0] = map.get(target - nums[i]);
          return result;
       } 
       map.put(nums[i], i);
    }

    return result;

   }

The tricky part is that the size of the result int[] is fixed. Because the problem assumes only one solution exists. The size must be 2. So no need to use ArrayList and once find one pair, can just return the result.

Use HashMap with element as the key and index in the array as the value. Be careful about the sequence of the index in the result array. The difference element should exist already so its index should be 0 in result int[].

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s