Задача: 930. Binary Subarrays With Sum
Сложность: medium

Если задан двоичный массив nums и целочисленная цель, верните количество непустых подмассивов с целью sum. Подмассив - это смежная часть массива.

Пример:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4

👨‍💻 Алгоритм:

1⃣Использовать словарь для хранения количества встреченных сумм префиксов.
Инициализировать текущую сумму и счетчик подмассивов с нулевыми значениями.

2⃣Пройти по массиву и обновить текущую сумму.
Если текущая сумма минус цель уже в словаре, добавить количество таких префиксов к счетчику подмассивов.
Обновить словарь префиксных сумм.

3⃣Вернуть счетчик подмассивов.

😎 Решение:
function numSubarraysWithSum($nums, $goal) {
$prefixSumCount = [0 => 1];
$currentSum = 0;
$count = 0;

foreach ($nums as $num) {
$currentSum += $num;
if (isset($prefixSumCount[$currentSum - $goal])) {
$count += $prefixSumCount[$currentSum - $goal];
}
if (isset($prefixSumCount[$currentSum])) {
$prefixSumCount[$currentSum]++;
} else {
$prefixSumCount[$currentSum] = 1;
}
}

return $count;
}

Ставь 👍 и забирай 📚 Базу знаний