[数据结构与算法]leetcode 930. 和相同的二元子数组

leetcode 930. 和相同的二元子数组

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

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

示例 1：

输入：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：

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

提示：

• 1 <= nums.length <= 3 * 10^4
• nums[i] 不是 0 就是 1
• 0 <= goal <= nums.length

方法一：哈希表 + 前缀和
思路：遍历nums，将当前位置的前缀和sum加入到map中，此时map中存储的是当前位置及其左侧的前缀和。此时，右边界为sum，区间和为goal，那么左边界为sum - goal ,即[sum - goal, sum]，所以只需累加 sum - goal的个数即可。

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int, int> map;
        int sum = 0;
        int cnt = 0;
        for(int x : nums){
            map[sum]++;
            sum += x;
            cnt += map[sum - goal];
        }
        return cnt;
    }
};

方法二：双指针+滑动窗口
思路：遍历nums，求当前位置的前缀和sum。当前的位置记为 r ，找到两个区间，第一：[ left , r ]，其区间和恰好等于goal；第二：[ left1, r ]，其区间和刚好小于goal； 那么 left1 - left 其实就是0的个数，使得[ left, left1 ) 的前缀和保持不变。

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();
        int sum = 0, sum1 = 0;
        int cnt = 0;
        int left = 0, r = 0, left1 = 0;
        while(r < n){
            sum += nums[r];
            sum1 += nums[r];
            //找到第一个等于goal的范围区间(left ~ r)的左侧位置left
            while(left  <= r && sum > goal){
                sum -=nums[left];
                left ++;
            }
            //找到第一个小于goal的范围区间(left1  ~ r)的左侧位置left1
            while(left1  <= r && sum1 >= goal){
                sum1 -= nums[left1];
                left1 ++;
            }
            cnt += left1  - left;
            r++;
        }
        return cnt;
    }
};