Увеличение скорости Sum of Pairs- Codewars

Question

Я только начал учиться программировать около 2 недель go и столкнулся с проблемой ниже. Изначально я написал код как двойной вложенный l oop, но, что неудивительно, истекло время ожидания. Я перекомпилировал свой код, чтобы (я думаю) иметь асимптотическое c время выполнения 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  

Проблема

Учитывая список целых чисел и одно значение суммы, верните первые два значения (проанализируйте, пожалуйста, слева) в порядке появления, в результате чего получается сумма.

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

Вот подход, который обеспечит вам линейное время выполнения:

• создайте отображение, которое связывает индекс первого вхождения каждого элемента массива.

• затем итерация по массиву для каждого индекса / значения:

  • если индекс больше, чем смещение текущего лучшего, разрыв с l oop.
  • , если сумма-значение находится в массиве: если его смещение меньше текущего лучшего, запомните пару.

• в конце этой итерации либо нет пар, либо у вас есть первая пара.