如何降低此python脚本的时间复杂性？

Question

以下是问题描述：

成对之和

给定一个整数列表和一个求和值，返回前两个值（请从左开始解析），它们按外观顺序相加形成求和

和对（[11,3,7,5]，10） =[3,7]

我的解决方案：

import collections

def sum_pairs(ints, s):
    beforenums = collections.defaultdict()
    for index_before, num in enumerate(ints[1:]):
        beforenums[ints[index_before]] = index_before
        try:
            r = beforenums[s-num]
        except KeyError:
            pass
        else:
            return [s-num, num]
        
    return None

这个解决方案是有效的，我能够把它降低到O（n）时间复杂度。有没有办法进一步缩短执行时间，我仍然在拖延代码战争。问题是，我将获得超过10000000个元素的列表。完整的问题可以在这里找到：https://www.codewars.com/kata/54d81488b981293527000c8f/train/python

Answer 1

您可以尝试使用set（）使其运行得更快

def sum_pairs(ints, s):
    cache = set()
    
    for x in ints:
        if s - x in cache:
            return [s-x, x]
        cache.add(x)

或者使用字典