Количество подмассивов с уникальной суммой с суммой не более K

Дан массив arr[] размера N и целое число K . Задача состоит в том, чтобы подсчитать количество подмассивов с уникальной суммой, сумма которых не превышает K.

Примеры :

Input: N = 3, arr[] = {1, 0, 1}, K = 1
Output: 3
Explanation: All Subarrays are [1], [0], [1], [1, 0], [0, 1], [1, 0, 1] & The sum of these subarrays are {1, 0, 1, 1, 1, 2} respectively. There are only 2 distinct possible sums less than or equal to 1
Input: N = 1, arr[] = {1}, K = 0
Output: 0

Подход : Задача может быть решена путем вычисления сумм каждого подмассива и сохранения их в HashMap . Перебрать HashMap и увеличить счетчик, если сумма не превышает K

Ниже приведена реализация вышеуказанного подхода

Временная сложность : O(N ² )
Вспомогательное пространство : O(N)