Given an array of integers, return indices of the two numbers such that they add up to a specific target.
Each input should have exactly one solution and you may not use the same element twice.
Example,
arr_nums = [7, 4, 2, 11, 20], target = 6
Here, arr_nums[1] + arr_nums[2] = 6
So, return [1, 2]
Let us use HashMap to solve this problem.
public int[] twoSum(int[] numbers, int target){
int[] arr = new int[2]; //an empty array to return the results
Map map = new HashMap();
/* map for numbers and index pair */
/* check if map has an elements which is equal to difference between current element and target */
for(int i=0; i<numbers.length; i++){
Integer val = map.get(target - numbers[i]);
if(val ==null){
map.put(numbers[i] i);
}else{
arr[0] = val;
arr[1] = i;
break;
}
}
return arr;
}
Time Complexity: O(N) , since the array has been traversed only once.
Space Complexity: O(1) + O(N), O(1) for variables and O(N) for the Hashmap.
The Web Spark 