930. 和相同的二元子数组

题目链接：https://leetcode.cn/problems/binary-subarrays-with-sum/

代码

/**
 * 930. 和相同的二元子数组
 * https://leetcode.cn/problems/binary-subarrays-with-sum/
 */

function numSubarraysWithSum(nums: number[], goal: number): number {
    // 恰好等于goal的数量 = 大于goal的数量 - 大于goal - 1的数量
    return solve(nums, goal) - solve(nums, goal - 1);
}

function solve(nums: number[], goal: number): number {
    if (goal < 0) return 0;
    let left = 0;
    let res = 0;
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        while (sum > goal) {
            sum -= nums[left];
            left++;
        }
        res += i - left + 1;
    }
    return res;
}

思路

使用滑动窗口 + 转化思想求解恰好和为 goal 的子数组个数：

核心思想：恰好等于 goal 的子数组数量 = 小于等于 goal 的子数组数量 - 小于等于 goal - 1 的子数组数量

对于辅助函数 solve(nums, goal)，计算和小于等于 goal 的子数组个数：

使用双指针 left 和 i 维护滑动窗口
用 sum 记录当前窗口内的和
当 sum > goal 时，收缩左边界直到 sum <= goal
此时以 i 为右端点的所有合法子数组数量为 i - left + 1（包含 [left, i], [left+1, i], ..., [i, i]）

通过两次调用 solve，即可得到恰好等于 goal 的子数组个数。

时间复杂度 $O (n)$ ，其中 $n$ 为数组长度
空间复杂度 $O (1)$

930. 和相同的二元子数组 ​

代码 ​

思路 ​

930. 和相同的二元子数组

代码

思路