Two Sum Array Problem (Leetcode)

You are given an array of integers named 'nums' and an integer value, you have to return the two numbers that equal 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.

Approach: Hashing is one of the approaches by which we can solve this problem. Here, use a hash map to check whether (target-x) is present in the map or not for each value x. If (target-x) is present in the map, then we can return the current number x’s index and (target-x)’s index.

This can be done in constant time.

Dry Run: We are given array, nums = [2,3,1,4], target = 4

• For index 0, x = 2, and as we know currently map is empty.
  • Now, find the value (target – x) = 4 – 2 = 2 is present in the map or not.
  • For now, 2 do not exist on the map.
  • And we store the index of element 2. i.e., mp[2] = 0,
• For index 1, x = 3
  • Again, find the value (target – x) = 4  – 3 = 1 is present in the map or not.
  • For now, 1 does not exist on the map.
  • And we store the index of element 3. i.e., mp[3] = 1,
• For index 2, x = 1 
  • Again, find the value  (target – i) = 4  – 1 = 3 is present on the map or not. 3 exits in the map, so we store index 2 and value stored for key 3 in the map and break the loop. And return [1,2]

Java solution

C++ Solution

Success

Details 

Runtime: 13 ms, faster than 87.98% of C++ online submissions for Two Sum.

Memory Usage: 10.9 MB, less than 46.19% of C++ online submissions for Two Sum.