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)