Problem Statement:
You are given an array of integers named 'nums' and an integer value, you have to return the pair of elements that equals to the given value.
Let's assume that each input would have only one solution and don't use the same element twice for pair add-up.
Don't bother about the order of your solution, return it in any order.
Example 1:
Input: nums = [2,6,10,13], target = 12 Output: [0,2] Explanation: Because nums[0] + nums[2] == 12, we return [0, 2].
Example 2:
Input: nums = [5,9,1], target = 10 Output: [1,2]
Example 3:
Input: nums = [5,5], target = 10 Output: [0,1]
Constraints:
2 <= nums.size() <= 104-109 <= nums[i] <= 109-109 <= target <= 109- Only one valid answer exists.
Whenever we compares one algorithm to another, there will be always some differences and some similarities. Here, in this approach, there is a difference in space.
To make it work faster we will create a new variable in the memory. We can declare an object like hashmap, named as numObj. Then we only iterate one time over the array,
but also with an additional variable named "compliment". As we know that if we add this number to the current iterating element would be equal to the target.
C++ SolutionTo make it work faster we will create a new variable in the memory. We can declare an object like hashmap, named as numObj. Then we only iterate one time over the array,
but also with an additional variable named "compliment". As we know that if we add this number to the current iterating element would be equal to the target.
class Solution{
public:
vetctor<int,int> twoSum(vector<int>&nums, int target){
vetor<int> ans;
for(int i=0; i<nums.size(); i++){
if(map.find(target-nums[i])!=map.end()){
ans.push_back(map[target-nums[i]]);
ans.push_back(i);
return ans;
}
map[nums[i]]=i;
}
return ans;
}
}
Java Solution
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result=new int[2];
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;
}
}
When you look at this approach, you will notice that this algorithm works fast as it takes fewer iterations. And in the worse case, it will take O(n) time complexity as it
will take as many iterations as the size of the array. This is the much better and faster way to execute!!
will take as many iterations as the size of the array. This is the much better and faster way to execute!!
Success
Details Runtime: 8 ms, faster than 57.68% of Java online submissions for Two Sum.
Memory Usage: 46.2 MB, less than 17.80% of Java online submissions for Two Sum.