Sum of pairs from list: memoization, design optimalization

From a list of integers and a single sum value, I have to return the first two values in order of appearance that adds up to the sum. source of the task

I think the most optimal way to scan the list is:

```
index 0, index 1
```
```
index 0,          index 2
```
```
         index 1, index 2
```
```
index 0,                   index 3
```
```
        index 1,           index 3
```
```
                  index 2, index 3
```

and so on. Am I right so far?

Then I used memoization to cut numbers appearing more than twice.

The code I wrote is functional but times-out on the more advanced tests. Here it is:

def sum_pairs(ints, s):
d={}
n2_index = 0
d[ints[0]] = 1
while True:
    n2_index += 1
    if ints[n2_index] not in d.keys():
        d[ints[n2_index]] = 0
        
    if d[ints[n2_index]] == 2:
        if n2_index == len(ints)-1:
            return None
        continue
    for n1_index in range (0, n2_index):

        if ints[n1_index] + ints[n2_index] == s:
            return [ints[n1_index], ints[n2_index]]
    
    d[ints[n2_index]] += 1
    
    if n2_index == len(ints)-1:
        return None

I would appreciate it greatly if you could help me understand my mistake/mistakes and how to approach this kind of task. Cheers!

Solution

The way to do this is to remember all the numbers you have seen before. This is normaly done in a set, a set is gives you O(1) (constant) look up time, so you determine very fast if you have seen a particular number or not already.

As you can through the list, you look in your set to see if you have seen the sum - current_value. If so you can output these two values, if not you add the current_value to the set and continue.

def sum(ints, s):
    seen = set()
    for current_value in ints:
        if s - current_value in seen:
             return s-current_value, current_value
        else:
             seen.add(current_value)
    return None