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].
Brute force solution
Take an item from array and look for target – that item in the array.
This will be an O(n^2) solution as we are trying to find pair for each element by looping through the remaining elements.
class TwoSum {
public int[] twoSum(int[] nums, int target) {
//loop through the array
for(int i = 0; i < nums.length; i++){
//fix the first element in the pair
int first = nums[i];
//loop through remaining elements to find the second
// element of the pair
for(int j = i+1; j < nums.length; j++){
//return the indices of the pair
if(first + nums[j] == target){
return new int[]{i, j};
}
}
}
//return empty array if not pair found
return new int[]{};
}
}
Optimized
Using a hashmap to look if target-key exists for every array element, if yes, we have found the pair. If no, then we add that key to hashmap.
Time complexity is O(n), using only one loop to traverse array of size n and space complexity is also O(n), hashmap storing all elements of array of size n
class TwoSumOptimized {
public int[] twoSum(int[] nums, int target) {
//Hashmap to store the nums[i] and i, where 0<i<nums.length
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
//loop through the array
for(int num = 0; num < nums.length; num++){
//find difference between target and nums[num]
int compliment = target - nums[num];
//if map contains the compliment then we have the result indices of num and map.get(compliment)
if(map.containsKey(compliment)){
return new int[]{map.get(compliment), num};
}
//put nums[num] and num in map as key, value pair
map.put(nums[num], num);
}
//return empty array if no pair found
return new int[]{};
}
}
Code – TwoSum.java and TwoSumOptimized.java
Source – leetcode
