[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:

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

和相同的二元子数组。

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

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

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

时间O(n)

空间O(1)

Java实现

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

sliding window相关题目

LeetCode 题目总结

[LeetCode] 930. Binary Subarrays With Sum

原文：https://www.cnblogs.com/cnoodle/p/14731886.html