Sliding Window Counting windows
182. Binary Subarrays With Sum
You are given an array nums in which every element is 0 or 1, and an integer k. Return the number of
subarrays that hold exactly k ones. In other words, count the subarrays whose elements add up to k.
A subarray is a contiguous sequence of elements from nums, with at least one element. Two subarrays are
different if they start or end at different positions.
Example 1
Input: nums = [1, 0, 1, 0, 0, 1], k = 2
5Explanation: Five subarrays hold exactly two 1s: [1,0,1], [1,0,1,0] and [1,0,1,0,0], which start at index 0, and
[0,1,0,0,1] and [1,0,0,1], which end at the last index.
Example 2
Input: nums = [0, 0, 1, 0], k = 0
4Explanation: With k = 0 only the subarrays made of 0s count. The first two 0s give [0] twice and [0,0] once, and
the last 0 gives one more [0].
Example 3
Input: nums = [0, 1, 0, 0], k = 2
0Explanation: The array holds only one 1, so no subarray holds two.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105nums[i]is0or10 ≤ k ≤ nums.length
Clarifying questions
What you would ask an interviewer before writing any code.