№560 leetcode Subarray Sum Equals K.
Есть массив чисел, и дано значение k. Надо найти все последовательные под-массивы сумма которых равна k.
В условиях также сказано, что числа в массиве могут быть как положительные, так и отрицательные. Если бы мы имели дело с числами с одинаковым знаком, то задача решалась бы с использованием скользящего окна. Но здесь надо искать какой то более общий подход.
Решение «в лоб» понятное и простое — мы перебираем все под-массивы, при этом можно оптимизировать перебор, накапливая сумму в цикле. Выглядит это так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
function subarraySum_brute(nums: number[], k: number): number { let count = 0; const cache: Map<number, number> = new Map(); for (let i = 0; i < nums.length; i ++) { let sum = 0; for (let j = i; j < nums.length; j ++) { sum += nums[j] if (sum == k) count ++; } } return count; }; |
Сложность, как видите, n^2.
Eсть и более производительное решение, которое не очень было понятно для меня, потому я его разберу подробнее.
По сути мы имеем дело с обнаружением величины k.
Это сумма некоторого под-массива, который начинается с индекса i и заканчивается индексом j. Мы можем выразить k через разницу между двумя суммами Σj и Σi. Где сумма Σx — это сумма всех элементов с начала массива до элемента с номером x.
Σj — Σi = k. (1)
Это идея позволяет нам реализовать следующий алгоритм.
Мы суммируем элементы массива последовательно в цикле, получая Σj — сумму элементов до рассматриваемого элемента, таким образом мы получаем все значения Σx, среди которых Σj и Σi.
На каждой итерации мы делаем три вещи:
- Очевидно, что надо проверить не равна ли текущая сумма k. Σx == k — один из искомых кейсов.
- Менее очевидно то, что надо проверить сколько раз мы уже набирали Σx = (Σj — k)
- Запоминаем сколько раз мы набрали Σj, формируя набор Σi.
Что мы делаем во 2ом пункте? Если на текущей итерации оказывается, что мы уже набирали сумму равную Σj — k, то именно столько под-массивов нужно добавить к текущему результату. Т.к. из формулы (1) следует, что
Σj — k = Σi (2)
И именно это нужно проверить.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
function subarraySum(nums: number[], k: number): number { // сигмы храним и подсчитываем, используя карту let sigmas: Map<number, number> = new Map(); // сумма для текещей итерации let sigmaJ = 0; // число подмассивов, удовлетворяющих условию задачи let count = 0; for (let num of nums) { sigmaJ += num; // 1. проверка Σj if (sigmaJ === k) count ++; // 2. проверка Σj - k if (sigmas.has(sigmaJ - k)) { count += sigmas.get(sigmaJ - k) as number; } // 3. добавление текущей Σj в массив const ex = sigmas.get(sigmaJ); if (ex === undefined) sigmas.set(sigmaJ, 1); else sigmas.set(sigmaJ, ex + 1); } return count; }; |