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

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 \leq$ nums.length $\leq10^3$

• $-10^5\leq$ nums[i] $\leq 10^5$

• $-10^5\leq$ k $\leq10^5$

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.

1. Initialize an empty unordered 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 unordered 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: