Хитрый Алгоритм: Решение задачи Continuous Subarray Sum

За последние две недели я занимался различными задачами на Leetcode. И сегодня я наткнулся на интересную задачу: Сумма последовательного подмассива - решением которой хотел бы с вами поделиться.

Изначально я попробовал решение методом грубой силы с временной сложностью O(n^2). Однако этот подход не сработал на тестах с большим входным массивом с около 200,000 элементами. Выполнение этого теста заканчивалось «Time Limit Exceed». Я потратил час на оптимизацию своего алгоритма и решил использовать кэш для хранения сумм, когда они меньше k. Эта оптимизация позволила мне пройти несколько дополнительных тестов, но самый большой входной набор все равно завершался ошибкой.

Тогда я обратился к разделу обсуждений и нашел интересное решение, предложенное другим пользователем

Код казался необычным, и даже непонятным, поэтому я решил его протестировать. К моему удивлению, он работал идеально!

Любопытствуя о механике алгоритма, я попросил ChatGPT объяснить его. Алгоритм оказался простым и понятным.

Вот как это работает:

Остатки:

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

Математическая Интуиция:

1. Представление Остатков:
   

   • Предположим, сумма элементов от начала до индекса i дает остаток r1 при делении на k.

   • Аналогично, сумма элементов от начала до более позднего индекса j (где j > i) также дает тот же остаток r1.

2. Разница Сумм:
   

   • Разница между этими двумя суммами, то есть (сумма элементов до j) - (сумма элементов до i), будет кратна k, потому что обе суммы оставляют один и тот же остаток при делении на k.

Обнаружение Подмассивов:

• Теперь непосредственно к коду. Когда мы обнаруживаем, что очередной остаток curr уже присутствует в множестве seen, это означает, что существует подмассив между этими двумя точками, сумма которого дает остаток 0 при делении на k. Иными словами, сумма этого подмассива кратна k.

Пример для ясности:

Рассмотрим массив nums = [23, 2, 4, 6, 7] и k = 6.

• Шаг 1: Сумма первого элемента 23 дает остаток 23 % 6 = 5.

• Шаг 2: Сумма первых двух элементов 23 + 2 = 25 дает остаток 25 % 6 = 1.

• Шаг 3: Сумма первых трех элементов 23 + 2 + 4 = 29 дает остаток 29 % 6 = 5.

На этом этапе мы замечаем, что остаток 5 уже был встречен на Шаге 1. Это указывает на то, что подмассив [2, 4] (от Шага 1 до Шага 3) имеет сумму, кратную 6.

---

Надеюсь, вам это показалось интересным. Алгоритм простой, несложный, изящный. Лишний раз я убедился, что иногда к решениям задач можно и нужно подходить нестандартно. Это позволяет их довольно эффективно решать.