Уровень: medium
Сегодня разберу задачку, в которой требуется найти количество подмассивов в массиве, сумма чисел которых равна некоторому числу k.
Итак, условие задачи: на вход мы получаем массив int[] nums и число k. Требуется найти количество подмассивов в массиве nums, сумма чисел в каждом из которых равняется числу k. Массив (и, соответственно, подмассив) - это непрерывная последовательность чисел.
Разберем на примере, что от нас хотят. Допустим, на вход мы получили следующие условия:
int[] nums = [1, 6, -5, 7, 2, 10, -8, 1], k = 2
Найдем, сколько существует подмассивов, сумма чисел в которых равна 2:
[1, 6, -5], [-5, 7], [2], [10, -8]
Ответ: 4.
p.s. сумма чисел в исходном массиве 1 (первый элемент) + 1(последний элемент) тоже равна 2, но это не удовлетворяет условию, что подмассив - это непрерывная последовательность чисел.
Ссылка на задачу тут. (https://leetcode.com/problems/subarray-sum-equals-k/description/)
Ограничения:
1. Длина массива от 1 до 2 * 10^4
2. Значения элементов массива от -1000 до 1000
3. Значения k от -10^7 до 10^7
Есть несколько подходов к решению:
- Первый способ решения
Проверять каждый подмассив, начиная с самого левого значения, постепенно двигая границу вправо. Если значение суммы станет равной искомому числу, то увеличить результат на единицу. Для реализации нам бы понадобилось два цикла - внешним мы бы двигали левую границу, а внутренним пробегались по остальным числам, находящимся справа от него, и суммировали бы их. На нашем примере это выглядело бы так:
[1, 6, -5, 7, 2, 10, -8, 1], k = 2
Шаг 1: Подмассивы, начинающиеся с числа 1: [1], [1,6], [1, 6,-5],[1, 6,-5,7], [1, 6,-5, 7, 2], [1, 6, -5, 7, 2, 10], [1, 6, -5, 7, 2, 10, -8], [1, 6, -5, 7, 2, 10, -8, 1]
Суммы каждого подмассива: 1, 7, 2 (совпало, увеличиваем результат), 9, 11, 21, 13, 14
Шаг 2: Подмассивы, начинающиеся с числа 6: [6], [6,-5],[6,-5,7], [6,-5, 7, 2], [6, -5, 7, 2, 10], [6, -5, 7, 2, 10, -8], [6, -5, 7, 2, 10, -8, 1]
Суммы каждого подмассива: 6, 1, 8, 10, 20, 12, 13 - ничего не совпало
И так далее мы бы двигали левую границу вправо, пока не достигли бы конца массива.
Временная сложность такого алгоритма составила бы О(n^2) - так как нам надо пройтись под каждому числу массива, которых n штук + по каждому числу, справа от него, т.е. еще по n.
Пространственная сложность: O(1), т.к. мы выделяем константное кол-во памяти под результат и под промежуточные суммы.
Код выглядел бы так:
public int subarraySum(int[] nums, int k) {
int result = 0;
for (int start = 0; start < nums.length; start++) {
int subarraySum = 0;
for (int end = start; end < nums.length; end++) {
subarraySum += nums[end];
if (subarraySum == k) {
result++;
}
}
}
return result;
}Второй способ решения
Способ называется подсчет суммы на префиксах, и для его реализации нам потребуется хэш-таблица. Что, собственно, мы будем делать:
1. Создаем хэш-таблицу, где будут храниться значения промежуточных сумм (отрезков) и их количество
2. Проходимся по значения массива, проверяя, есть ли в нашей хэш таблице значение отрезка, который можно отсечь, чтобы получилось число k.
3. Если есть, увеличиваем результат на единицу
4. Добавляем сумму чисел нового (текущего) отрезка в хэш-таблицу
На нашем примере это было бы так:
Шаг 1:
Хэш-таблица на начало работы шага: [0,1] - позже объясню, почему там лежит эта пара
- Отрезок: [1]
- Промежуточная сумма: 1
- Искомый отрезок на отсечение в хэш-таблице: 1 - 2 = -1 (такого не существует)
- Результат (финальный): 0
- Записываем в хэш-таблицу значение [1,1], где ключ (1) - текущее значение отрезка, значение (1) - кол-во таких отрезков
Шаг 2:
Хэш-таблица на начало работы шага: [0,1],[1,1]
- Отрезок: [1,6]
- Промежуточная сумма: 7
- Искомый отрезок на отсечение в хэш-таблице: 7 - 2 = 5 (такого нет)
- Результат (финальный): 0
- Записываем в хэш-таблицу значение [7,1], где ключ (7) - текущее значение отрезка, значение (1) - кол-во таких отрезков