[LeetCode] 930. Binary Subarrays With Sum

In an array A of 0s and 1s, how many non-empty subarrays have sum S?

Example 1:

Input: A = [1,0,1,0,1], S = 2
Output: 4
Explanation: 
The 4 subarrays are bolded below:
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]

Note:

A.length <= 30000
0 <= S <= A.length
A[i] is either 0 or 1.

和相同的二元子数组。

题意是在由若干 0 和 1 组成的数组 A 中，有多少个和为 S 的非空子数组。

如果你对题目够敏感，会发现这道题可以用滑动窗口或者前缀和的思路去解决。这一类的题一般两种方法都可以做。我这里提供一个滑动窗口的做法，思路很像992题，可以放在一起做。

一般滑动窗口的题目问的是满足条件的子数组最多有多少，或者是满足题意的子数组的长度最多是多长。但是这道题，以及992题，问的是满足题意的子数组的条件是恰好满足某个条件。所以这里会利用到一个helper函数，计算最多有多少个子数组的和为 S + 1 以及计算最多有多少个子数组的和为 S。两者的差值就是有多少个子数组的和正好为 S。

时间O(n)

空间O(1)

Java实现

 1     public int numSubarraysWithSum(int[] nums, int goal) {
 2         return helper(nums, goal) - helper(nums, goal - 1);
 3     }
 4 
 5     private int helper(int[] nums, int limit) {
 6         int res = 0;
 7         int sum = 0;
 8         int len = nums.length;
 9         int start = 0;
10         int end = 0;
11         while (end < len) {
12             sum += nums[end];
13             end++;
14             while (start < end && sum > limit) {
15                 sum -= nums[start];
16                 start++;
17             }
18             res += end - start + 1;
19         }
20         return res;
21     }
22 }

sliding window相关题目

LeetCode 题目总结