Сложность: medium
Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.
Пример:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
👨💻 Алгоритм:
1⃣Использовать словарь для хранения количества встреченных сумм префиксов.
Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.
2⃣Пройти по массиву и обновить текущую сумму.
Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов.
Обновить словарь префиксных сумм.
3⃣Вернуть счетчик подмассивов.
😎 Решение:
def numSubarraysWithSum(nums, goal):
prefix_sum_count = {0: 1}
current_sum = 0
count = 0
for num in nums:
current_sum += num
if current_sum - goal in prefix_sum_count:
count += prefix_sum_count[current_sum - goal]
if current_sum in prefix_sum_count:
prefix_sum_count[current_sum] += 1
else:
prefix_sum_count[current_sum] = 1
return count
Ставь 👍 и забирай 📚 Базу знаний