Solution: Find Two Numbers That Add up to k—Hashing

Let’s solve the Find Two Numbers That Add up to k—Hashing problem.

We'll cover the following

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:

  • 2≤2 \leq nums.length ≤103\leq10^3

  • −105≤-10^5\leq nums[i] ≤105\leq 10^5

  • −105≤-10^5\leq k ≤105\leq10^5

Solution 1: Using a hash map

The algorithm uses a hash 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 hash 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 hash map for future lookups.

  1. Initialize an empty hash map, foundValues, that will store the elements of the nums as keys.

  2. Iterate through each element, num, in nums. For each element, perform the following steps:

    1. Calculate the complement, which is k - num. The complement represents the value that, when added to num, gives the target sum k.

    2. Check whether the complement is already in foundValues. If it is, it means that num and its complement together form the target sum, k. In this case, return a pair of the complement and the current element, [complement, num].

    3. If the complement is not found in foundValues, add the current element num as a key to the hash map with a corresponding value, 0. The value 0 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 70+ hands-on prep courses.