Списки алгоритмов с python

Question

Я пытаюсь найти алгоритм для решения следующей проблемы с python.

Given a list of integers, check if after dropping two elements of the list, is it possible to divide the list in 3 where the sum of the consecutive numbers are equals.

Например:
A = [1, 3, 4 , 2, 2, 2, 1, 1, 2 ] должен возвращать TRUE , потому что мы отбросим элементы, выделенные жирным шрифтом, список может быть разрезан на [1, 3], [2, 2], [2, 1, 1] , где вся сумма 4

B = [1, 1, 1, 1, 1, 1] должна возвращать ЛОЖЬ

C = [1, 1, 3, 1, 1, 1034 , 5, 9900 , 1, 2] должно также возвращает FALSE , потому что, хотя после удаления чисел, выделенных жирным шрифтом, вы можете суммировать числа для суммирования 5 (1,1,3), (5), (1, 1, 1, 2) список должен быть отсортированным первым, а это недопустимо.

Я пришел с решением, которое, кажется, работает, но оно очень, очень плохое и не уверен, всегда ли оно работает, а сложность слишком высока, когда должно быть O (n) Я не знаю, как итеративно удалить 2 числа из списка, не имея сложности O (n ^ 2)

Th анкс

Answer 1

Действительно, можно решить эту проблему в O(n) (при условии, что целые числа положительные), где n - размер вашего массива A.

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

Вот код python, выполняющий это:

def find_couple_list_sum(int_list):
    n = len(int_list)
    left_sum = [0 for _ in range(n)]
    for i in range(1, n):
        left_sum[i] = left_sum[i-1] + int_list[i-1]

    right_sum = [0 for _ in range(n)]
    for j in range(n-2, -1, -1):
        right_sum[j] = right_sum[j+1] + int_list[j+1]

    total_sum = sum(int_list)
    print(left_sum)
    print(right_sum)
    print(total_sum)
    i, j = 0, n-1
    while True:
        print(i, j)
        mid_sum = total_sum - left_sum[i] - right_sum[j] - int_list[i] - int_list[j]
        if left_sum[i] == right_sum[j] and left_sum[i] == mid_sum:
            return i, j
        elif i == j:
            return None, None
        elif left_sum[i] < right_sum[j]:
            i += 1
        else:
            j -= 1


int_list = [1, 3, 4, 2, 2, 2, 1, 1, 2]
print(find_couple_list_sum(int_list))

Все это действительно работает в O(n).