Задача о поиске всех подходящих под-сум

№560 leetcode Subarray Sum Equals K.

Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k.

В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если бы мы имели дело с числами с одинаковым знаком, то задача решалась бы с использованием скользящего окна. Но здесь надо искать какой то более общий подход.

Решение «в лоб» понятное и простое — мы перебираем все под-массивы, при этом можно оптимизировать перебор, накапливая сумму в цикле. Выглядит это так:

Сложность, как видите, n^2.

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

По сути мы имеем дело с обнаружением величины k.

Это сумма некоторого под-массива, который начинается с индекса i и заканчивается индексом j. Мы можем выразить k через разницу между двумя суммами Σj и Σi. Где сумма Σx — это сумма всех элементов с начала массива до элемента с номером x.

Σj — Σi = k. (1)

Это идея позволяет нам реализовать следующий алгоритм.

Мы суммируем элементы массива последовательно в цикле, получая Σj — сумму элементов до рассматриваемого элемента, таким образом мы получаем все значения Σx, среди которых Σj и Σi.

На каждой итерации мы делаем три вещи:

  1. Очевидно, что надо проверить не равна ли текущая сумма k. Σx == k — один из искомых кейсов.
  2. Менее очевидно то, что надо проверить сколько раз мы уже набирали Σx = (Σj — k)
  3. Запоминаем сколько раз мы набрали Σj, формируя набор Σi.

Что мы делаем во 2ом пункте? Если на текущей итерации оказывается, что мы уже набирали сумму равную Σj — k, то именно столько под-массивов нужно добавить к текущему результату. Т.к. из формулы (1) следует, что

Σj — k = Σi (2)

И именно это нужно проверить.

Написать комментарий

Мало букафф? Читайте есчо !

Подсчет кол-ва нулевых подмассивов

Март 21, 2023 г.

Разбор задачи с литкода. (2348. Number of Zero-Filled Subarrays). Суть: есть массив чисел, нужно подсчитать кол-во подмассивов, состоящих из нулей. Например, дан массив [0, 0, 1]. Как видим, есть последовательность из двух нулей в начале ...

Читать

Задача о подмножествах

Апрель 21, 2023 г.

В теории программирования большой класс задач связан с перебором подмножеств, и на leetcode как раз попалась пара похожих задач, чтобы можно было их разобрать как пример - 78 Subsets и 90 Subsets II. Формулировка следующая - есть набор (множество) ...

Читать

 

Комментарии к «Задача о поиске всех подходящих под-сум»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: