和相同的二元子数组

题目

给你一个二元数组 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 * 104
  • nums[i] 不是 0 就是 1
  • 0 <= 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)。

© 版权声明
THE END
喜欢就支持一下吧
点赞7 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片快捷回复

    暂无评论内容