Максимальное количество подмассивов различных размеров с заданной суммой
Учитывая двоичный массив arr[] из N целых чисел, задача состоит в том, чтобы найти максимальное количество подмассивов различных размеров, чтобы сумма каждого подмассива была K .
Пример:
Input: arr[] = {0, 1, 1 , 0}, K = 2
Output: 3
Explanation: The subset {{0, 1, 1, 0}, {0, 1, 1}, {1, 1}} is the subset of 3 subarrays such that the sum of each subarray is 2 and the size of each subarray is distinct. The subarray {1, 1, 0} also has sum 2 but a subarray of size 3 is already included.Input: arr[] = {0, 1, 0, 0, 0, 1 , 0}, K = 1
Output: 5
Подход: Данную задачу можно решить с помощью алгоритма скользящего окна. Можно заметить, что сумма подмассива равна количеству единиц в подмассиве. Ниже приведены шаги, которые необходимо выполнить:
- Поддерживайте переменную, которая отслеживает количество единиц в текущем окне.
- Если количество единиц в текущем окне меньше K , увеличьте размер окна, и аналогично, если количество единиц больше K , уменьшите размер окна.
- Для окон с суммой K вставьте их размер в заданную структуру данных.
- Требуемым ответом является количество элементов в наборе после обхода всего массива.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(N)