Число подмассивов, в которых сумма элементов равна k

Дан целочисленный массив и целое число k. Найти количество непрерывных подмассивов таких, что сумма их элементов равна k.

Пример 1:

Дано: nums = [1,1,1], k = 2
Результат: 2

Условия:

• Длинна массива находится в диапазоне [1, 20,000].
• Элементы массива находятся в диапазоне [-1000, 1000], число k - в диапазоне [-1e7, 1e7].

Идея решения

Если кумулятивная сумма (пусть $sum[i]\; -\; это$сумма с нулевого до $i^{th}$ индекса) одинакова для индексов i и j, значит, сумма между этими двумя индексами равна нулю. А если суммы в индексах $i$ и  $j$ таковы, что $sum[i] - sum[j] = k$, значит, сумма элементов между индексами $i$ and $j$ равна $k$.

Создадим хэшмап $map$, чтобы хранить кумулятивные суммы для всех индексов, вместе с количеством того, сколько раз мы посчитали эту сумму. То есть это пары $(sum_i, no. of occurences of sum_i)$. Каждый раз, когда мы встречаем новую сумму, мы создаем новый ключ в хэшмапе, который соответствует этой сумме. Если опять нам удасться посчитать эту сумму, мы увеличиваем счётчик, который ей соответствует. 

Далее, для каждой посчитанной суммы, мы смотрим, сколько раз нам встретилась сумма $sum-k$, потому что это указывает на то, сколько раз нам встретился подмассив с суммой элементов = $k$ . И переменную $count$, которую мы должны возвратить, мы увеличиваем на это значение.

После того, как мы обошли весь массив, мы возвращаем $count$.

Имплементация

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap < Integer, Integer > map = new HashMap < > ();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
} 

Сложность алгоритма

• Сложность по времени: $O(n)$. Элемента массива $nums$ мы просматриваем только один раз.

• Сложность по памяти : $O(n)$. Хэшмап $map$ может содержать не более $n$ различных элементов в худшем случае.