Блог

Главная - Вопросы по программированию - Пытаюсь найти элемент в массиве, из которого сумма элементов слева равна элементам справа. Не могли бы вы оптимизировать мой подход?

Пытаюсь найти элемент в массиве, из которого сумма элементов слева равна элементам справа. Не могли бы вы оптимизировать мой подход?

#python #python-3.x #list

Вопрос:

 def balancedSums(arr):
    n = len(arr)
    for i in range(0, n):
        lsum = sum(arr[0 : i])
        rsum = sum(arr[i   1 : n])
        if lsum == rsum:
            return "YES"
    return "NO"

Я получаю все тестовые примеры, кроме двух, с ошибкой из-за тайм-аута. Каковы мои варианты?

Комментарии:

1. Вы могли бы продолжать подсчитывать итоги во время итерации, вместо того чтобы складывать всю левую и правую стороны на каждом повороте. Вы могли бы избежать составления фрагментов своего списка.

2. Откуда это взялось? Пожалуйста, дайте ссылку.

Ответ №1:

Вы можете сделать что-то подобное:

 def balancedSums(arr):
    lsum = 0
    rsum = sum(arr)
    n = len(arr)
    for i in range(0, n):
        rsum -= arr[i]
        if lsum == rsum:
            return "YES"
        lsum  = arr[i]
    return "NO"

Сложность этого во времени заключается в O(n)

Комментарии:

1. да, конечно. Спасибо за предупреждение

2. @хелвуд иг, это было то, к чему он стремился. В любом случае, у меня есть идея.

3. @DanielHao, могу я спросить вас, почему это так?

4. @don’talkjustcode, мой код использует те же шаги, что и его… первая итерация ничего не добавляет к левой сумме lsum

5. @Анварвик. Хорошо, теперь это работает. Но в моем тесте это в 3 раза медленнее (и больше строк), чем код операции!

Ответ №2:

Я попытался придумать векторизованный способ сделать это с помощью Numpy. Это лучшее, что я придумал до сих пор:

 import numpy as np

def balancedSums(arr):
    arr = np.array(arr)
    ltr = np.cumsum(arr)
    rtl = np.cumsum(arr[::-1])[::-1]
    if np.any(ltr == rtl):
        return "YES"
    else:
        return "NO"

assert(balancedSums([1, 2, 3]) == "NO")
assert(balancedSums([3, 2, 1, 2, 3]) == "YES")
assert(balancedSums([10]) == "YES")
assert(balancedSums([1, 1]) == "NO")
assert(balancedSums([0]) == "YES")
assert(balancedSums([]) == "NO")

Комментарии:

1. Забудь об этом! Это примерно в 8 раз медленнее, чем ответ @Anwarvic.

2. Ладно, у меня sum там было кое-что. Теперь это примерно в 20 раз быстрее, чем ответ @Anwarvic.

3. в 20 раз быстрее на каких данных?

4. Что-то вроде rtl = ltr[-1] - ltr , возможно, могло бы быть немного быстрее.

5. Да, это снизило его до ~6,5 мс.

Метки: ,