python - 增加对和的速度 - Codewars

Question

我大约 2 周前才开始学习编码，遇到了以下问题。我最初将代码编写为双嵌套循环，但不出所料地超时了。我重新编译了我的代码，以便(我认为)具有 O(n) 的渐近运行时间而不是 O(n^2)。我正在寻找使我的代码更快的方法:

def sum_pairs(ints, s):
    minn = min(ints)
    if s < 0:
        minn +- s
    if minn > 0:
        minn = 0
    maxx = max(ints)
    if s > maxx:
        maxx = s
    ans = [0] * 2
    arr = [0.5] * (maxx-2*minn +1)
    for i in range (0, len(ints), 1):
        target = s - ints[i]
        if target >= minn:
            if not arr[target-minn] == 0.5:
                ans[0] = target
                ans[1] = ints[i]
                return ans
        arr[ints[i]-minn] = i
    return None  

问题

Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that adds up to form the sum.

sum_pairs([11, 3, 7, 5], 10)

           ^--^      3 + 7 = 10

== [3, 7]

sum_pairs([4, 3, 2, 3, 4], 6)

       ^-----^         4 + 2 = 6, indices: 0, 2 *
          ^-----^      3 + 3 = 6, indices: 1, 3
             ^-----^   2 + 4 = 6, indices: 2, 4

* 整对较早，因此是正确答案== [4, 2]

https://www.codewars.com/kata/54d81488b981293527000c8f/train/python

Answer 1

这里有一种方法可以让您获得线性执行时间:

• 创建一个映射，关联每个数组元素第一次出现的索引。

• 然后为每个索引/值迭代数组:

  • 如果索引大于当前最佳的偏移量，则跳出循环。
  • 如果和值在数组中:如果其偏移量小于当前最佳值，则记住该对。

• 在此迭代结束时，要么没有对，要么您有第一对。