Solution: Find Two Numbers That Add up to k—Hashing
Let’s solve the Find Two Numbers That Add up to k—Hashing problem.
Statement
Given an array of integers nums
and an integer target, k
, find two numbers in the array that sum up to the target k
.
There is exactly one solution for each input, and each element of the array can only be used once in the solution. The order of the returned elements does not matter.
Constraints:
nums.length
nums[i]
k
Solution 1: Using an unordered map
The algorithm uses an unordered map to store the traversed values and their complements needed to reach k
. We iterate through the array and check if the complement of the current element is in the unordered map. If it is, we return the current element and its complement as a pair that sums to k
. Otherwise, we add the current element to the unordered map for future lookups.
Initialize an empty unordered map,
foundValues
, that will store the elements of thenums
as keys.Iterate through each element,
num
, innums
. For each element, perform the following steps:Calculate the complement, which is
k - num
. The complement represents the value that, when added tonum
, gives the target sumk
.Check whether the complement is already in
foundValues
. If it is, it means thatnum
and its complement together form the target sum,k
. In this case, return a pair of the complement and the current element,[complement, num]
.If the complement is not found in
foundValues
, add the current elementnum
as a key to the unordered map with a corresponding value,0
. The value0
doesn’t carry any significance; it’s just used to indicate that the element has been encountered.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.