Two Sum — Asked in Facebook, Google, and Amazon Interviews
Problem Statement :
You are given an array of integers of length ’n’ and an integer ‘x’. Your task is to return a pair of elements such that they add up to ‘Target’.
The first line contains two integers, integer ’n’, denoting the number of elements, and integer ‘x’, denoting the ‘Target’.
The next line contains the array of numbers from where we have to consider the numbers.
4 92 7 11 13
Explanation of given Test Cases :
For the given test case, we can see that the sum of 2 and 7 is equal to 9 and it is the only valid pair.
This problem can be solved efficiently by using the technique of hashing. Use a hash_map to check for the current array value x(let). If there exists a value target_sum - x, which on adding to the former gives, target_sum, print out that value pair.
This can be done in constant time.
Time Complexity : O(N)
Space Complexity : O(N)