The Self-Taught Computer Scientist

Data Structures
144
Inside your function, you create a dictionary:
a_dict = {}
Then, you call 
enumerate
on the list, which allows you to iterate through the list while keeping 
track of each number and its index in the list:
for index, n in enumerate(a_list):
Next, you subtract 
n
from the target number:
rem = target - n
The result is the number the current number needs to match with to add up to the target number 
you are looking for. If the number in the variable 
rem
is in your dictionary, you know you’ve found 
the answer, so you return the current index and look up the index of the number you stored using 
the key 
rem
inside your dictionary:
return index, a_dict[rem]
If the number in the variable 
rem
is not in your dictionary, you add it to your dictionary, putting 
n
as the key and its index as the value:
else:
a_dict[n] = index 
Let’s take a look at how this works. Say you ran your program with this list and a target number of 5:
[- 1, 2, 3, 4, 7]
The first time around your loop, 
n
is −1 and nothing is in your dictionary, so you add −1 at index 
0 to your dictionary. The second time around your loop, 
n is 2, so 
rem
is 3 (5 − 2), so this time you 
add 2 at index 1 to your dictionary. The third time around your loop, 
n
is 3, which means 
rem
is 2. 
You already put 2 in your dictionary, which means you’ve found the answer.
Unlike your brute- force approach to solving your problem, this solution is O(
n) because using a 
hash table means you no longer have to use two nested 
for
loops, so it is much more efficient.
Vocabulary
associative array: An abstract data type that stores key- value pairs with unique keys.
key- value pair: Two pieces of data mapped together: a key and a value.