Сумма подряд идущих

Question

Пытаюсь решить задачу (сложность должна быть линейной ):

Дан массив целых чисел a[1],a[2],...,a[n] и натуральные числа k и m. Укажите минимальное значение i, для которого a[i]+a[i+1]+...+a[i+k]=m (то есть сумма k+1 подряд идущих элементов массива равна m). Если такого значения нет, то выведите 0.

Входные данные:

4 1 22

9 13 10 -11

Выходные данные:

Написал вот такой код:

n,k,m = map(int,input().split())

a = list(map(int,input().split()))


p = [0] * (n + 1)

for i in range(1, n + 1):
    p[i] = p[i - 1] + a[i -1]

p.pop(0)



if m not in p:
    print('0')

else:
    e = p.index(m)
    if p[k] == m:
        print(e)
else:
    print(0)

Но программа не проходит все тесты. Заранее спасибо

Answer 1

Считаете сумму первых k+1 элементов

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

summ = summ - a[i-1] + a[i + k]
проверить summ

Код

res = 0
summ = sum(a[:k+1])
if summ == m:
    res = 1
else:
    for i in range(1, n - k):
        summ += a[i+k]-a[i-1]
        if summ == m:
            res = i + 1
            break
print(res)

БЛОГ НА HUSL

Сумма подряд идущих

Ответы (1 шт):