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

Question

从一个整数列表和一个和值中，我必须按照外观的顺序返回前两个值，然后相加为和。任务的来源

我觉得最优化的扫单方式是：

1. index 0, index 1
   

   index 0,          index 2
   

            index 1, index 2
   

   index 0,                   index 3
   

           index 1,           index 3
   

                     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