Хэш-таблица на начало работы шага: [0,1],[1,1],[7,1]
- Отрезок: [1,6, -5]
- Промежуточная сумма: 2
- Искомый отрезок на отсечение в хэш-таблице: 2 - 2 = 0 (вот его-то мы и добавили в начале!!!)
Мы всегда заранее добавляем в хэш-таблицу значение (0, 1), чтобы не пропустить подмассив, когда не нужно ничего отсекать.
- Результат (финальный): 1
- Записываем в хэш-таблицу значение [2,1], где ключ (2) - текущее значение отрезка, значение (1) - кол-во таких отрезков
Шаг 4:
Хэш-таблица на начало работы шага: [0,1], [1,1],[7,1],[2,1]
- Отрезок: [1,6, -5, 7]
- Промежуточная сумма: 9
- Искомый отрезок на отсечение в хэш-таблице: 9 - 2 = 7 (такой есть - это сумма с шага 2 - [1,6]), если мы отсечем этот отрезок, то останется отрезок [-5,7] - сумма чисел которого равняется 2.
- Результат (финальный): 2
- Записываем в хэш-таблицу значение [9,1], где ключ (9) - текущее значение отрезка, значение (1) - кол-во таких отрезков
Шаг 5:
Хэш-таблица на начало работы шага: [0,1],[1,1],[7,1],[2,1],[9,1]
- Отрезок: [1,6, -5, 7, 2]
- Промежуточная сумма: 11
- Искомый отрезок на отсечение в хэш-таблице: 11 - 2 = 9 (такой есть)
- Результат (финальный): 3
- Записываем в хэш-таблицу значение [11,1], где ключ (11) - текущее значение отрезка, значение (1) - кол-во таких отрезков
Продолжаем так пока не дойдем до конца массива.
Теперь изобразим в коде:
public int subarraySum(int[] nums, int k) {
int result = 0;
int subarraySum = 0;
Map<Integer, Integer> prefixSumCount = new HashMap();
prefixSumCount.put(0, 1);
for (int num: nums) {
subarraySum += num;
int partToBeRemoved = subarraySum - k;
result += prefixSumCount.getOrDefault(partToBeRemoved, 0);
prefixSumCount.put(subarraySum, prefixSumCount.getOrDefault(subarraySum, 0) + 1);
}
return result;
}Временная сложность такого алгоритма составит O(n) - в два раза быстрее!! т.к. мы проходим по каждому элементу массива всего 1 раз.
Пространственная сложность (да, похуже) - O(n), т.к. нужна память под хэш-таблицу, и в худшем случае она будет пропорциональна кол-ву элементов.