# Find all the pairs in a list that are summing to a known number

## posted May 2014

I got asked this question in an interview. And I knew this question beforehands, and that it had to deal with hashtables, but never got to dig into it since I thought nobody would asked me that for a simple internship.

I didn't know how to answer, in my mind I just had a simple php script that would have looked like this:

```
$arr = array(-5, 5, 3, 1, 7, 8);
$target = 8;
for($i = 0; $i < sizeof($arr) - 1; $i++)
{
for($j = $i + 1; $j < sizeof($arr); $j++)
{
if($arr[$i] + $arr[$j] == $target)
echo "pair found: ${arr[i]}, ${arr[j]}";
}
}
```

But it's pretty slow, it's mathematically correct, but it's more of a CS-oriented question. How to implement that quickly for machines? The answer is **hash tables**. Which are implemented as **arrays** in PHP (well, arrays are like super hash tables) and as **dictionaries** in Python.

I came up with this simple example in python:

```
arr = (-5, 5, 3, 1, 7, 8)
target = 8
dic = {}
for i, item in enumerate(arr):
dic[item] = i
if dic.has_key(target - item) and dic[target - item] != i:
print item, (target - item)
```

- iterate the list
- assign the hash of the value to the index of the value in the array
- to avoid finding a pair twice, we do this in the same for loop:

we do the difference of the target sum and the number we're on, we hash it, if we find that in the hash table that's good! - but it could also be the number itself, so we check for its index, and it has to be different than its own index.

VoilĂ ! We avoid the n-1! additions and comparisons of the first idea with hash tables (I actually have no idea how fast they are but since most things use hash tables in IT, I guess that it is pretty fast).