只差一点点

这就是最好的时代

【LeetCode.930】和相同的二元子数组

分类于

题目：和相同的二元子数组

​ 给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。

​ 子数组 是数组的一段连续部分。

示例 1：

1
2
3
4
输入：nums = [1,0,1,0,1], goal = 2
输出：4
解释：
有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2：

1
2
输入：nums = [0,0,0,0,0], goal = 0
输出：15

提示：

1 <= nums.length <= 3 * 104

nums[i] 不是 0 就是 1

0 <= goal <= nums.length

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    //滑动窗口法
    //右指针逐渐向右，左一指针找到第一个符合的位置，左二指针找到最后一个符合的位置
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int left1 = 0, left2 = 0;
        int n = nums.size();
        int sum1 = 0, sum2 = 0;
        int ret = 0;

        for(int right = 0; right < n; right++){
            sum2 += nums[right];
            sum1 += nums[right];
            while(left2 <= right && sum2 >= goal){
                sum2 -= nums[left2];
                left2++;
            }

            while(left1 < left2 && sum1 > goal){
                sum1 -= nums[left1];
                left1++;
            }

            ret += left2 - left1;
        }

        return ret;
    }
};

易错点：

1.提示2nums[i] 不是 0 就是 1，所以不用判断相等的情况if(sum == goal)

2.三个只指针对应的大小关系，其中left1 <= left2 <= right <= nums.size()