本文详解如何正确统计二进制数组中和恰好等于 goal 的非空连续子数组数量，重点剖析滑动窗口法失效的根本原因，并基于“1 的间隔建模”思想给出时间复杂度 O(n)、逻辑完备的数学解法，特别处理 goal = 0 这一关键边缘情况。
本文详解如何正确统计二进制数组中和恰好等于 goal 的非空连续子数组数量，重点剖析滑动窗口法失效的根本原因，并基于“1 的间隔建模”思想给出时间复杂度 O(n)、逻辑完备的数学解法，特别处理 goal = 0 这一关键边缘情况。
在 leetcode 第 930 题 Binary Subarrays With Sum 中，核心挑战并非单纯实现滑动窗口，而在于正确建模子数组的组合自由度。原始代码尝试用双指针维护当前窗口和，但其逻辑存在根本性缺陷：当 sumSoFar == goal 时仅单向扩展 j 或收缩 i，却忽略了此时窗口左右两侧的零元素可独立伸缩——这导致大量合法子数组（如 [0,0,0,0] 中所有长度 ≥1 的全零子数组）被遗漏，尤其在 goal = 0 时错误尤为显著（示例中期望 15，实际输出 10）。
问题本质：从“枚举窗口”到“组合计数”
关键洞察在于：每个满足和为 goal 的子数组，必然恰好包含 goal 个 1，且其起始与结束位置由这些 1 周围的零元素决定。我们可将数组按 1 分割，提取出所有“间隙长度”（gap），即每两个相邻 1 之间的零元素个数加 1（首段前导零个数 +1，末段后缀零个数 +1）。例如：
nums = [0,0,0,0,1,0,1,0,0,1,0] # 1 的索引：4, 6, 9 → gaps = [5, 2, 3, 2] # 解释：[0,0,0,0] → 4+1=5；4→6间有1个0 → 1+1=2；6→9间有2个0 → 2+1=3；9之后有1个0 → 1+1=2- 当 goal > 0：一个有效子数组必须覆盖第 k 个 1 到第 k+goal-1 个 1。其左边界可在第 k 个 1 左侧任意一个零位置开始（共 gaps[k] 种选择），右边界可在第 k+goal-1 个 1 右侧任意一个零位置结束（共 gaps[k+goal] 种选择）。因此，对每个 k，贡献为 gaps[k] * gaps[k+goal]。
- 当 goal = 0：子数组不能含任何 1，只能取纯零段。长度为 L 的连续零段可构成 L*(L-1)//2 个非空子数组（即从 L 个位置选 2 个端点的组合数，等价于三角形数）。
完整实现与验证
class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: # 步骤1：构建 gap 数组 —— 每个元素表示一段连续零的长度+1 gaps = [] j = 0 # 上一个 1 出现后的下一个位置 for i, val in enumerate(nums): if val == 1: gaps.append(i - j + 1) # 当前1到上一个1（或开头）的距离（含左侧零个数+1） j = i + 1 gaps.append(len(nums) - j + 1) # 末尾零段长度+1 # 步骤2：分情况计算 if goal == 0: # 对每个纯零段，计算其内部非空子数组数：L*(L-1)//2 return sum(gap * (gap - 1) // 2 for gap in gaps) else: # 滑动长度为 goal 的窗口：gaps[k] * gaps[k+goal] return sum(before * after for before, after in zip(gaps, gaps[goal:])) # 测试用例验证 sol = Solution() print(sol.numSubarraysWithSum([1,0,1,0,1], 2)) # 输出: 4 ✅ print(sol.numSubarraysWithSum([0,0,0,0,0], 0)) # 输出: 15 ✅ print(sol.numSubarraysWithSum([0,0,0,0,1,0,1,0,0,1,0], 2)) # 输出: 19 (15+4) ✅注意事项与总结
- 时间/空间复杂度：仅需一次遍历构建 gaps 数组，后续计算为 O(n)，整体为 O(n) 时间，O(n) 空间（gaps 最坏长度为 n+1）。
- 边界鲁棒性：该解法天然处理 goal = 0、goal > sum(nums)（此时 gaps[goal:] 为空，sum() 返回 0）、空数组等所有边缘情况。
- 避免常见误区：
- ❌ 不要试图用传统滑动窗口“动态调整”左右边界来覆盖所有组合——零的伸缩是正交的，必须用乘法原理；
- ❌ 构建 gaps 时务必在首尾都 +1，以正确计数边界位置的选择数（例如 [1] 应得 gaps = [1,1]）；
- ✅ goal = 0 的三角形数公式 L*(L-1)//2 是核心，不可简化为 L*L 或其他近似。
此方法将问题升维至“结构分析”层面，通过预处理数组的稀疏特征（1 的分布），将子数组计数转化为简洁的代数运算，是解决此类“带约束的连续子序列计数”问题的范式级思路。