За последние две недели я занимался различными задачами на Leetcode. И сегодня я наткнулся на интересную задачу: Сумма последовательного подмассива - решением которой хотел бы с вами поделиться.
Изначально я попробовал решение методом грубой силы с временной сложностью O(n^2). Однако этот подход не сработал на тестах с большим входным массивом с около 200,000 элементами. Выполнение этого теста заканчивалось «Time Limit Exceed». Я потратил час на оптимизацию своего алгоритма и решил использовать кэш для хранения сумм, когда они меньше k. Эта оптимизация позволила мне пройти несколько дополнительных тестов, но самый большой входной набор все равно завершался ошибкой.
Тогда я обратился к разделу обсуждений и нашел интересное решение, предложенное другим пользователем
Код казался необычным, и даже непонятным, поэтому я решил его протестировать. К моему удивлению, он работал идеально!
Любопытствуя о механике алгоритма, я попросил ChatGPT объяснить его. Алгоритм оказался простым и понятным.
Вот как это работает:
Остатки:
При вычислении остатка от деления суммы подмассива на k, мы можем встретить тот же остаток в разных точках при прохождении массива. Это повторение остатков является ключевым для определения подмассивов, сумма которых кратна k.
Математическая Интуиция:
-
Представление Остатков:
Предположим, сумма элементов от начала до индекса
iдает остатокr1при делении наk.Аналогично, сумма элементов от начала до более позднего индекса
j(гдеj > i) также дает тот же остатокr1.
-
Разница Сумм:
Разница между этими двумя суммами, то есть
(сумма элементов до 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.
Надеюсь, вам это показалось интересным. Алгоритм простой, несложный, изящный. Лишний раз я убедился, что иногда к решениям задач можно и нужно подходить нестандартно. Это позволяет их довольно эффективно решать.
Комментарии (23)
wataru
09.06.2024 09:53+15Вы бы почитали раздел с решениями, там часто человеческим языком написано. Ваше (вернее GPT-шное) объяснение весьма слабое.
Как выше уже вам сказали - тут применятеся "кумулятивная сумма". Это надо для каждого элемента подсчитать сумму от начала массива. Очень во многих задачах на отрезки в массиве оно взникает. Потому что любой отрезок - это разница двух префиксов: [l,r]= [0,r] - [0,l-1]. Поэтому сумма, xor, произведение и еще много чего на отрезке вырождается в операцию над всего двумя числами в массиве этих кумулятивных вычислений.
В этой задаче сумма подмассива должна делиться на k, т.е. разность sum[r]-sum[l-1] должна делиться на k, а это происходит, только когда эти 2 числа дают одинаковый остаток по модулю k. Это тоже частый прием в задачах: если у вас фигурирует делимость, то стоит обратить внимание на остатки по модулую k.
Ну вот, у вас получилась задача подсчитать все пары одинаковых чисел в массиве из кумулятивных сумм (не стоящих рядом, чтобы длина подмассива была хотя бы 2).
А тут уже можно по разному делать. Можно идти по массиву слева-направо и отслеживать, какие числа у вас уже встречались и сколько. Или можно отсортировать массив. Можно массивы длины 1 тоже подсчитать и в конце их все вычесть. А можно числа подсчитывать с задержкой в одну операцию, как в приведенном вами коде (переменная prev).
Ну и отдельно - минус в карму вам за разнесение по интернету отрыжки ChatGPT. Пользы вы не принесли, а только энтропию повысили. Кому надо - сами у него спросят. Не засоряйте интернет, пожалуйста. Это очень хороший интсрумент, но имеющий свою область применения. Вы должны его вывод сначала переварить, понять и проверить. И только после этого можно уже разносить по интернету свои мысли, идеи или знания. Можно на ChatGPT даже не ссылаться уже, ибо это ваши слова, за которые вы отвечаете.
alexstich Автор
09.06.2024 09:53+1Честно говоря, до раздела с решениями я не добрался. Потом в него зашел после написания статьи. Там как раз все обьясняется подробно. Так как алгоритмы я не так давно решаю, то мне такое лаконичное и интересное решение, особенно после долгого времени его решения, очень впечатлило, поэтому и написал статью. За фидбек спасибо. Учту.
aamonster
09.06.2024 09:53+1Ну, кумулятивные суммы тут уже упомянули, и понятно, что тут их применяешь автоматически – шаг 1.
Нам важна только делимость суммы на k, значит, все кумулятивные суммы считаются по модулю k – шаг 2.
Нам нужно найти сумму, кратную k – т.е. две равные кумулятивные суммы – шаг 3.Итого за три шага, каждый из которых делается автоматически, не думая, получаем практически готовое решение (осталось только отследить, чтобы две одинаковые суммы, которые мы ищем, были не подряд).
Да, такие формальные методы не всегда дают готовое решение – но они часто упрощают задачу без каких-либо усилий.
ЗЫ: А если хотите реально интересную задачку на обработку массивов – попробуйте самостоятельно вывести алгоритм скользящего максимума (массив, хотим для каждого элемента вычислить максимум из окна длиной N вокруг него). Быстродействие не должно зависеть от размера окна.
Алгоритм интересен, в частности, тем, что додумались до него очень поздно, емнип где-то в 80-е. При этом он достаточно прост, хоть и не так очевиден, как для вашей задачки, не думая – его не изобретёшь.
Alexandroppolus
09.06.2024 09:53Да, с максимумом прикольная задача, каноничный пример амортизированной сложности. Она кстати есть на первой странице списка хардов, можно сразу и отослать.
Sdima1357
09.06.2024 09:53+1Ещё он даёт свертку с прямоугольной функций, повторенная несколько раз даёт хорошее приближение к гауссиану.( central limit teorem) На 2д, гауссиан сепарабельный, то есть пожно сделать отдельно по горизонтали и по вертикалиЯ этим пользуюсь для быстрого замыливания картинки и получения ДОГ ( разность гауссианов) особых точек для регистрации видеоизибражений в реалтайм
Question_man
09.06.2024 09:53+1Эта задача вчерашняя daily. Тоже решил за O(n^2), но закономерно уперся в TL (иначе это была бы Easy задача). Спасибо за такой красивый алгоритм!
У меня еще идея такая была:
1. Сначала посчитать сумму элементов всего массива (O(n) без учета суммирования длинных чисел)
2. Запустить рекурсию: на каждом шаге отнимаем от суммы либо левый конец, либо правый
3. Идем либо до того, как сумма становится кратна k, либо до 0
4. Результируем с помощью конъюнкции
Но я ее не тестил)alexstich Автор
09.06.2024 09:53Да, daily.
Я, как написал в статье, стал кэшировать позицию и сумму, в том случае когда сумма подмассива была <k а потом становилась > k. Чтобы повторно не считать ее. Но это сработало только на частном случае. Там тест был с массивом [1,1,1...1,1,1,99999]. Вот его я прошел. А потом опять встал.
А этот алгоритм я когда увидел, я сначала думал, что чувак прикололся. Но потом посмотрел решение и решил поделиться, так как оно интересное )
Question_man
09.06.2024 09:53+1Попробовал реализоваать идею, получилось так (пришлось сделать причудливую мемоизацию, но напоролся на Memory Limit в этот раз):
class Solution: def checkSubarraySum(self, nums: List[int], k: int) -> bool: if len(nums) < 2: return False self.numbers = nums s = sum(self.numbers) self.cache = {} return self.checkSubarraySumRec(s, k, 0, len(nums) - 1) def checkSubarraySumRec(self, s, k, l, r) -> bool: if (l, r) in self.cache: return False if r - l == 0: self.cache[(l, r)] = True return False if s % k == 0: self.cache[(l, r)] = True return True self.cache[(l, r)] = True return self.checkSubarraySumRec(s - self.numbers[l], k, l + 1, r) or \ self.checkSubarraySumRec(s - self.numbers[r], k, l, r - 1)Словарь разбухает быстро. На 2000000000 элементах забивается весь хип. Оставлю этот код здесь, мб кто-нибудь придумает оптимизацию.
wataru
09.06.2024 09:53+1Не поможет эта "оптимизация". У вас все еще n^2 различных отрезков. Тупо 2 цикла сработают за точно такое же время (O(n^2)), надо только сумму считать подряд для всех отрезков с одинаковым началом. И не надо ни рекурсии, ни кеширования:
for l in range (0, n): sum = 0 for r in range (l, n): sum += numbers[r] # сумма на отрезке l..r - sumЭто все-равно, в тайм лимит не влезет, ибо нужно решение хотя бы за O(n log n).
Alexandroppolus
09.06.2024 09:53+1Почему-то задача напомнила эту
wataru
09.06.2024 09:53+1Интересная задача. Тоже ясно, что надо работать по модулю. И, раз уж мы в этой теме - то тоже через частичные суммы.
решение
Интересный факт: 32=2*3+5*3+11, а 11000 = 2^3*5^3*11
Поэтому докажем, что из n чисел можно составить число, делящееся на n, а потом получим 11000, перемножив 3 решения для 2, 3 решения для 5 и 1 решение для 11.
Рассмотрим частичне суммы по модулю n: их n. Если среди них есть 0, то можно взять сумму этого префикса и домножить на остальные числа. Иначе у нас n сумм, из которых все от 1 до n-1. По принципу Pigeonhole, получается, что там есть 2 одинаковых числа, а значит какой-то отрезок дает в сумме 0 по модулю n. Опять, его суммируем, а остальные числа слева и справа домножаем.
Можно было посложнее сделать задачку, взяв какое-то другое число или сделав побольше чисел в строке. А так после разложениея на множители сразу очевидно решение через декомпозицию.
Alexandroppolus
09.06.2024 09:53Можно было посложнее сделать задачку, взяв какое-то другое число или сделав побольше чисел в строке
Это только немного усложнит вычисления. Всё равно первое, что тут приходит в голову - разложить число на простые.
Но вообще там бывало так, что из-за маленьких чисел нельзя было разглядеть красивую общую идею, например тут
vesper-bot
09.06.2024 09:53Тупой вопрос: в условии задачи разрешен ли k==0? А то алгоритм хорош, но конкретно вот тут сломается. Решать можно будет тем же способом, но вместо остатков пихать в множество полную сумму (повторение будет указывать, что найден подмассив с суммой ==0 и можно получить его длину).
Alexandroppolus
09.06.2024 09:53По ссылке на задачу, в условиях есть Constraints, там 1 <= k <= 2^31-1
wataru
09.06.2024 09:53А что, по-вашему, означает "делится на 0"? Вы, похоже, считаете, что 0-то на 0 делится, а вот все остальное - нет. Но на самом деле, на ноль делить вообще нельзя.
vesper-bot
09.06.2024 09:53А там не "делится на k" а "a multiple of k", и для нуля таких чисел ровно одно - ноль.
domix32
09.06.2024 09:53+1В алгоритме надо хранить остаток от деления префикса, то бишь суммы элемента от нулевого до текущего. Если у нас в сохраненных остатках есть такой, то мы можем его отбросить, формируя валидный подмассив. Соотвественно количество остатков увеличивается, после добавления. НО, есть жирный нюанс с вычислением остатков - есть две операции - modulus и euclidean remainder и одно считает честные остатки от деления, а другое "наименьшее положительное остатка от деления". Собственно, для решения задачи требуется именно последнее. У питона оно используется по-умолчанию, а вот в других языках (по большей части касается случаев компилируемых) используется более быстрый остаток от деления. Поэтому для них придётся исхитриться и считать по формуле
В итоге алгоритм решается за O(n)
Решение на rust
impl Solution { pub fn subarrays_div_by_k(nums: Vec<i32>, k: i32) -> i32 { let sz = nums.len(); // можно легко доказать что размер кэша // не превысит k, т.к. значения наших остатков // всегда считается по mod k, поэтому вместо // HashMap можно использовать просто вектор let mut mods = vec!(0; k as usize); mods[0] = 1; // для случая когда элементов 0 let mut ret = 0; // возвращаемое количество let mut curr = 0; // сумма текущего префикса for n in nums.into_iter() { curr += n; // у Rust есть встроенный остаток // % k на отрицательных числах будет // выдавать иные значения let modulo = curr.rem_euclid(k) as usize; // добавляем количество найденных префиксов // которые мы можем удалить ret += mods[modulo]; // обновляем счётчик остатков текущим префиксом mods[modulo] += 1; } ret // возвращаем количество } }
AnnaElli
09.06.2024 09:53Красивое решение, но curr лишний, можно сразу в prev писать. Если числа в массиве могут быть отрицательными, то нужны доработки.
wataru
09.06.2024 09:53но curr лишний, можно сразу в prev писать
Нельзя. Иначе вы будете считать подмассивы длиной 1, а в задаче надо хотя бы длины 2 искать. prev как раз создает задержку, чтобы предыдущая частичная сумма не учитываласть для текущего числа. Или надо дополнительно где-то вычесть количество чисел, делящихся на k в изначальном массиве, чтобы убрать лишние подмассивы из подсчитанного ответа.
Если числа в массиве могут быть отрицательными, то нужны доработки.
По условию - не могут. Но доработка элементарная:
curr = ((prev + num) % k + k) % k- надо просто помнить, что операция взятия по модулю может вернуть число от -k+1 до k-1.
AspisVipera
Это целое семейство задач на кумулятивную сумму массива. Стоить вскрыть одну и все остальные становится очень просто решать.
amphasis
Кумулятивная сумма действительно сразу приходит в голову, но лично у меня не сразу щелкнуло, что сумму можно сразу считать по модулю
wataru
Ну как только вы поймете, что вам надо найти пары чисел с одинаковым остатком в массиве кумулятивных сумм - там уже пол жажочка осталось додуматься, что можно сразу по модулю брать.