Description

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:

Code

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

Use hashmap to speed up the searching. Image you have two queus:

arry list stores all memebers, which is nums –> A = [2, 4, 6, 8, 10, 12, 14, 16]
a hashmap, that stores member as key, position in array list as value. B = HashMap<Integer, Interger>

Now, let’s loop arry A, we will able to calculate anotherNum (target - value of member) for each member of A. if we could find anotherNum in HashMap B, then we have the answer, otherwise store member as well as its’ position into HashMap.

Code

java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int[] result = null;
        int anotherNum = -1;
        for(int i = 0;i < nums.length; i++){
            anotherNum = target - nums[i];
            if(map.containsKey(anotherNum)){
                result = new int[]{i, map.get(anotherNum)};
                return result;
            }else{
                map.put(nums[i],i);
            }
        }
        return result;
    }
}