Задача: 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;
}

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