Написано: 28.03.2023

813. Двоичный подмассив с суммой (Binary Subarrays With Sum)

medium

Задание.

Дан двоичный массив nums и целочисленную goal

Верните количество непустых подмассивов, в которых сумма равна goal.

Подмассив – это непрерывная часть массива.

Пример 1.

Входные данные: nums = [1,0,1,0,1], goal = 2

Результат: 4

Пояснение:

4 подмассива выделены шрифтом [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1]

Пример 2.

Входные данные: nums = [0,0,0,0,0], goal = 0

Результат: 15

Решение.

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        
    }
};

Способ решения

Подход 1: Индекс единиц

Предположим, мы пронумеруем единицы в A: (x1, x2, … xn), где A(xi) = 1