Problem: 930. 和相同的二元子数组

思路

滑动窗口

解题过程

我们可以通过计算 和大于等于 goal 的子数组数目 与 和大于等于 goal+1 的子数组数目 的差值，来得到 和恰好等于 goal 的子数组数目。

Code

c++

class Solution {
public:int at_most(vector<int>& nums, int goal) {int ans = 0;int n = nums.size();int l = 0;int sum = 0;for(int r = 0; r < n; r ++){sum += nums[r];while(sum >= goal && l <=r){sum -= nums[l];l++;}ans += l;}return ans;}int numSubarraysWithSum(vector<int>& nums, int goal) {return at_most(nums, goal) - at_most(nums,goal+1);}
};

python

class Solution:def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:def at_most(goal):ans = 0n = len(nums)l = 0sum = 0for r, x in enumerate(nums):sum += xwhile sum >= goal and l <= r:sum -= nums[l]l += 1ans += lreturn ansreturn at_most(goal) - at_most(goal + 1)

复杂度

• 时间复杂度: O(n)O(n) O(n)

• 空间复杂度: O(1)O(1) O(1)