How do you solve the Two Sum problem, and what is the complexity of your approach?
You keep a dictionary of the values you have already seen, and you look for the number that completes the pair.
def two_sum(nums, target):
seen = {}
for i, value in enumerate(nums):
complement = target - value
if complement in seen:
return (seen[complement], i)
seen[value] = i
return None
So how does it work? For each number, you work out what the other number in the pair would have to be. If you have already seen that number, then you have found the pair. If you have not, then you remember this number and go on to the next one.
So the complexity is O of n for the time, because you go through the list once and each step is a constant amount of work. And it is O of n for the space, because the dictionary can hold one entry for every number in the list.
There is one detail worth knowing about the order of the two steps. You look for the complement first, and you only then remember the value. If you did it the other way round, then a list with the same number twice and a target of twice that number would find the number with itself instead of the pair of two different places.
The next two questions in this topic look at the sorted version and at the harder variation.