Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the target.
Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the target.
Solution :
[class Solution {
public int[] twoSum(int[] nums, int target) {
int[] output = new int[2];
int n = nums.length;
HashMap<Integer, Integer> freq = new HashMap<>();
for (int i = 0; i < n; i++){
freq.put(nums[i],i);
}
System.out.println(freq);
for (int i = 0; i < n; i++){
int b = target - nums[i];
if (freq.containsKey(b) && freq.get(b) != i){
output[0] = freq.get(b);
output[1] = i;
return output;
}
}
return output;
}
}
]
Explanation :
We solve this problem by an optimised approach using O (N) time complexity. The questions tell us that we have to return an array of two numbers where array[num1] + array[num2] == target.
Also num1 != num2. We first create a hashmap with integer and their indexes. Then we assume that we already have num1.
To get num2 the formula becomes array[num2] = target - array[num1]. Now we use this formula and iterate over the array.
Now we assume num1 as i, get the value of num2 and search the hashmap for the value of num2. If we find the value of num2 in hashmap, we get its index and add it to the output array with index i and return the array.
Let me know what you think in comments below.
COMMENTS