Есть ли какие-нибудь советы, чтобы сделать мой Python код быстрее для Hackerrank?

Question

Я пытаюсь решить проблему с кодированием для Hackerrank, но постоянно сталкиваюсь с ошибками тайм-аута, поскольку мой код слишком долго запускается. Я знаю, что он работает отлично, отступы не проблема, в коде нет ничего «плохого». Мне просто нужны советы о том, как я могу заставить его работать более эффективно:

def main(n, o, q, m): 
    for x in m:
        for y,z in enumerate(o):
            x -= z
            if x<=0:
                print y+1
                break
        if x>0: print -1

o и m - это список целых чисел, которые циклически вычитаются из значений o из m, пока m не станет меньше 0, l oop заканчивается, а m по-прежнему не меньше 0, и будет напечатано -1. Конечная цель состоит в том, чтобы найти, какой int из o заканчивается m.

Answer 1

Вы выполняете вычитания, используя o для каждого l oop из m.

. Для повышения производительности вам нужно либо l oop m меньше, либо l oop o Меньше.

Один из циклов o Меньше - это предварительный расчет всех частичных сумм.

x имеет значения из o вычтенными. Возможно, вы вычтете только одно число, или два, или тысячу. Кто знает? И вы будете делать это для каждого l oop из m.

Например, если бы x были 10, а o были [2, 4, 6, 8], третий член был бы тем, что завершило l oop, третий член - 12, сумма 2, 4 и 6.

. Составление списка частичных сумм означает, что сложение необходимо выполнить только один раз.

itertools.accumulate может сделать это за вас.

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

Однако, если значения o все положительные, вы можете выполнить двоичный поиск частичных сумм.

См. этот ответ до Python двоичная поисковая функция для поиска первого числа в отсортированном списке, который больше указанного c значения