Python | Sliding Window | Префиксные суммы

Question

Задача: найти количество подмассивов равных 3-м

def foo(data=[1, 2, 2, 1], target=3):

    prefix_sum = defaultdict(int)
    prefix_sum[0] = 1
    count = 0
    current_sum = 0
    
    for right in range(len(data)):
        current_sum += data[right]
        difference = current_sum - target

        if difference in prefix_sum:
            count += prefix_sum[difference]
        prefix_sum[current_sum] += 1

    return count

Я не понимаю: если разница есть в словаре префиксных сумм, а разница это difference = текущая накопленная сумма - target, то значит увеличиваем count на 1, что значит, что между difference в словаре и target есть разница которая есть в словаре. Я не понимаю этого механизма. На 2-й итерации мы находим разницу 0, она есть в словаре, что это значит? Что между current_sum(3) и target есть... что есть? Я не понимаю этого механизма.

Answer 1

Что у нас хранится в словаре? Пары psum:счётчик, где psum - величина префиксной суммы.

На начальном этапе у нас есть только нулевая сумма, пока она одна. При проходе по списку, если в списке есть отрицательные числа, префиксные суммы с определённым значением могут встретиться несколько раз. Например:

 data    1, 2, -1, 1, -2, 3, -2, -1, 1
 ps   0  1  3   2  3   1  6  4   3   4
 cnt  1  1  1   1  2   2  1  1   3   2
            a      ^      b
                   здесь мы встретили сумму 3 во второй раз

Когда на второй итерации (a) мы нашли, что разность 0 есть в словаре со счётчиком 1, то получается, что диапазон 0:1(включительно) даёт пару индексов, между которыми сумма подмассива равна target (3), добавляем к результату 1.

Когда на шестой итерации (b) мы нашли, что разность 3 есть в словаре со счётчиком 2 - это означает, что имеется два диапазона, кончающиеся на индексе 5, которые дают сумму подмассива, равную target, поэтому результат будет увеличен на 2 (значение счётчика из словаря)

БЛОГ НА HUSL

Python | Sliding Window | Префиксные суммы

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