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

Statement

Given a list of integers nums and an integer target, k, find two numbers in the list that sum up to the target k.

There is exactly one solution for each input, and each element of the list 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 a dictionary

The algorithm uses a dictionary to store the traversed values and their complements needed to reach k. We iterate through the list and check if the complement of the current element is in the dictionary. 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 dictionary for future lookups.

1. Initialize an empty dictionary, found_values, 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 found_values. 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 found_values, add the current element num as a key to the dictionary 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: