题目
给你一个二元数组 nums ,和一个整数 goal ,请你统计并返回有多少个和为 goal 的 非空 子数组。
子数组 是数组的一段连续部分。
题目来源:https://leetcode.cn/problems/binary-subarrays-with-sum
示例
示例 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 * 104nums[i]不是0就是10 <= goal <= nums.length
题解
分析
先来看一个问题:某班有 10 个人至少 20 岁,至少 21 岁的有 3 个人,那么恰好 20 岁的人有多少个?
想必很快就能算出答案:至少 20 岁我们可以分为恰好 20 岁和至少 21 岁两部分,所有恰好20岁的人就有 10 - 3 = 7 个人。即答案为 7.
同理,这道题要求我们求出和恰好为 goal 的非空子数组的个数,我们可以将问转换为求非空子数组的和 >= goal 的个数和非空子数组的和 > goal 的个数。最后两数相减就得到了和恰好为 goal 的非空组数组个数。
由于本题 nums[i] 均为非负数,子数组越长,元素和越大,所以是「越长越合法」的计数滑窗问题。一般要写 ans += left
内层循环结束后,[left,right] 这个子数组是不满足题目要求的,但在退出循环之前的最后一轮循环,[left−1,right] 是满足题目要求的。由于子数组越长,越能满足题目要求,所以除了 [left−1,right],还有 [left−2,right],[left−3,right],…,[0,right] 都是满足要求的。也就是说,当右端点固定在 right 时,左端点在 0,1,2,…,left−1 的所有子数组都是满足要求的,这一共有 left 个。
代码
class Solution {
public:
int numSubarraysWithSum(vector<int>& nums, int goal) {
int ans = 0, left1 = 0, left2 = 0;
int sum1 = 0, sum2 = 0;
for (int right = 0; right < nums.size(); right++) {
sum1 += nums[right];
sum2 += nums[right];
while (left1 <= right && sum1 >= goal) { // 避免 goal = 0 的情况下标越界
sum1 -= nums[left1++];
}
ans += left1; // 加上 >= goal 的个数
while (sum2 > goal) {
sum2 -= nums[left2++];
}
ans -= left2; // 减去 > goal 的个数
}
return ans;
}
};
复杂度分析
时间复杂度:O(n),其中 n 是 nums 的长度。虽然写了个二重循环,但是内层循环中对 left1 加一的总执行次数不会超过 n 次,对 left2 加一的总执行次数不会超过 n 次,所以总的时间复杂度为 O(n)。
空间复杂度:O(1)。




暂无评论内容