930. 和相同的二元子数组

🎯 问题描述（来源于LeetCode）

描述：
给定一个二元数组 nums（只包含 0 和 1）和一个整数 goal，统计并返回具有和 goal 的非空连续子数组的个数。

说明：

  • 子数组是连续的。
  • 1 <= nums.length <= 3 * 10^4。

示例：

  • 示例 1：
1
2
3
输入: nums = [1,0,1,0,1], goal = 2
输出: 4
解释: 有 4 个子数组满足和等于 2。
  • 示例 2：
1
2
输入: nums = [0,0,0,0,0], goal = 0
输出: 15

💻 解题思路

思路：滑动窗口 + 容斥原理（基于您的代码）

算法步骤

  1. 定义辅助函数 getNums(k)，该函数返回数组中和大于等于 k 的连续子数组个数。
  2. 在 getNums(k) 中：
    • 初始化左指针 left = 0，当前窗口和 pre = 0，答案 ans = 0。
    • 遍历右指针 right，将 nums[right] 加入 pre。
    • 当 pre >= k 时，不断移动左指针（并将移出的元素从 pre 中减去），直到 pre < k。
    • 此时，对于当前右端点 right，所有左端点 小于 left 的子数组（即从 0 到 left-1 开始的子数组）的和都满足 >= k。因此，共有 left 个以当前 right 为结尾的合法子数组，将 left 累加到 ans。
  3. 利用容斥原理：sum == goal 的数量 = sum >= goal 的数量 - sum >= goal+1 的数量。因此返回 getNums(goal) - getNums(goal+1)。

代码实现（您的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from typing import List

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        def getNums(k: int) -> int:
            ans = 0
            left = 0
            pre = 0
            for right, num in enumerate(nums):
                pre += num
                while left <= right and pre >= k:
                    pre -= nums[left]
                    left += 1
                ans += left 
            return ans
        
        return getNums(goal) - getNums(goal + 1)

📊 性能分析

  • 时间复杂度：O(n)O(n)，每个元素最多被左右指针各访问一次（两次遍历，常数倍）。
  • 空间复杂度：O(1)O(1)，仅使用常数个变量。

思考

解法非常精妙！

  • 传统的滑动窗口通常直接统计“和小于 k”或“和不超过 k”的子数组个数。而您的 getNums 反其道而行之，通过 while pre >= k 收缩窗口，巧妙地统计了“和大于等于 k”的子数组个数。
  • 关键在于 ans += left：当窗口和小于 k 时，left 之前的每一个位置作为起点，与当前 right 组成的子数组，其和都必然大于等于 k。这正是因为包含这些起点会使得窗口扩大，从而恢复 >= k 的状态。
  • 这种写法避开了处理 0 元素带来的复杂边界条件，是本题的一种优雅且高效的解法。