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

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

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

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

😎 Решение:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);
        int currentSum = 0;
        int count = 0;
        
        for (int num : nums) {
            currentSum += num;
            count += prefixSumCount.getOrDefault(currentSum - goal, 0);
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }
        
        return count;
    }
}

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