列表中的对总和：记忆化、设计优化

Question

从整数列表和单个总和值中，我必须 return 前两个值按出现顺序加起来等于总和。 source of the task

我认为最佳的扫描列表方式是：

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

等等。到目前为止我说得对吗？

然后我用memoization减少了出现两次以上的数字。

我编写的代码可以正常运行，但在更高级的测试中超时。在这里：

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

如果您能帮助我理解 mistake/mistakes 以及如何处理此类任务，我将不胜感激。干杯！

Answer 1

方法是记住你以前见过的所有数字。这通常在一组中完成，一组为您提供 O(1)（常数）查找时间，因此您可以非常快速地确定是否已经看到特定数字。

正如您可以通过列表一样，您查看您的集合以查看您是否已经看到 sum - current_value。如果是这样，您可以输出这两个值，如果不是，则将 current_value 添加到集合中并继续。

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

列表中的对总和：记忆化、设计优化

Sum of pairs from list: memoization, design optimalization

python

design-patterns

memoization