时间戳

首页 > 解决方案 > 列表中的对总和：记忆，设计优化

python - 列表中的对总和：记忆，设计优化

问题描述

从整数列表和单个总和值中，我必须按出现的顺序返回前两个值，加起来就是总和。任务来源

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

  1. index 0, index 1

  2. index 0,          index 2

  3.          index 1, index 2

  4. index 0,                   index 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

如果您能帮助我理解我的错误/错误以及如何处理此类任务，我将不胜感激。干杯!

标签： pythondesign-patternsmemoization

解决方案

做到这一点的方法是记住你以前见过的所有数字。这通常在一组中完成，一组给你 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

推荐阅读