930. 和相同的二元子数组（多指针滑动窗口）

本文主要是介绍930. 和相同的二元子数组（多指针滑动窗口），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

多指针滑动窗口
滑动窗口，由于题目中数组为二元组数组，对于每一个数组下标 j ，当其满足 preSum[j]−preSum[i]=goal的条件时，对应 i为一个连续区间，若能够求得 i 的左右边界 left1 与 left2，则此时共有 left2−left1个子数组满足条件。

因此构建一个滑动窗口，随着其右边界 j 右移，其相应的两个左边界 left1与 left2也会随之移动。在移动过程中，我们要找到这两个左边界，使得 [left1,left2) 区间内任一数组下标 i 到滑动窗口的右边界j 的子数组之和为 goal。两个左边界通过窗口之和 sum1与 sum2 求取，当窗口之和 sum1 大于目标值时，left1 右移。当窗口之和 sum2 大于等于目标值时，left2 右移。

class Solution {
public:int numSubarraysWithSum(vector<int>& nums, int goal) {int res=0;int left1=0,left2=0,right=0,n=nums.size();long long tmp1=0,tmp2=0;while(right<n){tmp1+=nums[right];tmp2+=nums[right];right++;while(left1<right && tmp1>goal){tmp1-=nums[left1];left1++;  }while(left2<right && tmp2>=goal){tmp2-=nums[left2];left2++;}res+=left2-left1;}return res;}
};

前缀和+hash
不过空间复杂度O(n)

class Solution {
public:int numSubarraysWithSum(vector<int>& nums, int goal) {int n=nums.size();int preSum=0,res=0;unordered_map<int,int>mp;mp[0]=1;for(int i=0;i<n;++i){preSum+=nums[i];res+=mp[preSum-goal];mp[preSum]++;}return res;}
};