列表中的对和:回忆录，设计优化

Question

从一个整数列表和一个和值中，我必须返回前两个值，并按相加的顺序排列。任务的来源

我认为浏览名单的最佳方法是：

1. 指数0，指数1
2. 指数0，指数2
3. index 1, index 2
4. 指数0，指数3
5. index 1, index 3
6. index 2, index 3

诸若此类。到目前为止我说得对吗？

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

我编写的代码是功能性的，但在更高级的测试中超时。下面是：

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

如果你能帮助我理解我的错误和如何处理这类任务，我将不胜感激。干杯!

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