本文详解如何正确统计二进制数组中和恰好等于 goal 的非空连续子数组数量，重点剖析滑动窗口法失效的边界场景（如全零数组），并引入“1的间隙建模”思想，给出时间复杂度 O(n)、逻辑严谨且可证明正确的解决方案。
本文详解如何正确统计二进制数组中和恰好等于 `goal` 的非空连续子数组数量，重点剖析滑动窗口法失效的边界场景（如全零数组），并引入“1的间隙建模”思想，给出时间复杂度 o(n)、逻辑严谨且可证明正确的解决方案。
在解决「和为 goal 的二进制子数组个数」问题时，直觉上容易尝试双指针滑动窗口——维护区间 [i, j) 的和，根据当前和与 goal 的关系动态收缩或扩展窗口。但该思路在 goal = 0 或存在连续零段时极易出错：当 j 到达数组末尾后，仅靠单向移动 i 无法覆盖所有以不同起始位置、相同右端点（或延伸右端点）构成的有效子数组，导致漏计（如 [0,0,0,0] 中 goal=0 时应得 10 个子数组，原代码仅返回 6）。
根本原因在于：子数组的合法性不只取决于和是否达标，更取决于“1”的分布结构。二进制数组中，每个子数组的和即为其所含 1 的个数。因此，和为 goal 的子数组，必严格包含 goal 个 1（若 goal > 0），且其左右边界可自由延展至相邻 1 之间的零段中。
由此引出核心洞察：
✅ 若 goal == 0：答案等价于所有全零连续子数组的个数之和。长度为 L 的零段贡献 L × (L−1) / 2 个非空子数组（即三角形数）。
✅ 若 goal > 0：枚举每组恰好包含 goal 个 1 的最短子数组（即两端均为 1，且内部恰有 goal−1 个 1），再计算其左右可扩展的零个数——左扩空间 = 左侧连续零个数 + 1，右扩空间 = 右侧连续零个数 + 1；二者乘积即为该组 1 所能生成的有效子数组总数。
实现上，我们首先预处理出 gaps 数组：记录每个 1 与其前一个 1（或数组开头）之间的距离（含左侧边界），最后补上末尾零段到数组末的距离。例如：
- nums = [0,0,0,0,1,0,1,0,0,1,0], goal = 2
- 1 的索引为 [4,6,9] → gaps = [5, 3, 3, 2]
（解释：开头到第1个1有4个零 → 距离为 4+1=5；4→6间有1个零 → 1+1=2？注意标准构造应为 [首1前零数+1, 1间零数+1, ..., 末1后零数+1]；更稳健定义见下方代码）
标准 gaps 构造逻辑如下：
- 遍历 nums，记录每个 1 出现的位置；
- gaps[0] = 第一个 1 的索引 + 1（即开头到首个 1 的可选左起点数）；
- gaps[i]（i≥1）= 第 i 个 1 与第 i−1 个 1 的索引差（即中间零个数 + 1）；
- gaps[-1] = n - 最后一个1索引（即末尾零段长度，因右端点可取至数组末，故无需 +1）。
但更简洁鲁棒的实现是统一处理：
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
# Step 1: 构建 gaps —— 每个元素表示「以某个1为右边界时，左侧可选起始位置数」
gaps = []
j = 0 # 上一个1出现后的下一个位置（初始为0）
for i, x in enumerate(nums):
if x == 1:
gaps.append(i - j + 1) # 从j到i（含）共i-j+1个位置可作为包含此1的子数组左端点
j = i + 1
gaps.append(len(nums) - j + 1) # 末尾零段：从最后一个1之后到数组末，+1因左端点可取j本身
if goal == 0:
# 全零段：每个gap代表一段连续零（长度= gap-1），其子数组数为 C(gap,2) = gap*(gap-1)//2
return sum(gap * (gap - 1) // 2 for gap in gaps)
else:
# 对每个起始1（对应gaps[i]），需匹配第i+goal个1（对应gaps[i+goal]）
# 左侧可选起点数 = gaps[i]，右侧可选终点数 = gaps[i+goal]
return sum(gaps[i] * gaps[i + goal] for i in range(len(gaps) - goal))✅ 关键验证：nums = [0,0,0,0,0], goal = 0
gaps = [6]（j初值0，遍历无1，最终 len(nums)-j+1 = 5-0+1 = 6）
6*5//2 = 15 → 正确。✅ nums = [1,0,1,0,1], goal = 2
遍历：i=0,x=1 → gaps.append(0-0+1)=1, j=1；i=2,x=1 → gaps.append(2-1+1)=2, j=3；i=4,x=1 → gaps.append(4-3+1)=2, j=5；最后 gaps.append(5-5+1)=1 → gaps = [1,2,2,1]
goal=2 → i=0: 1*2=2; i=1: 2*1=2 → 总和 4 → 正确。
注意事项总结：
- ❌ 避免使用传统双指针滑动窗口直接维护和，因其无法同时兼顾多起点/多终点的组合爆炸；
- ✅ gaps 数组本质是对输入的结构化压缩，将问题转化为组合计数，时间复杂度严格 O(n)，空间 O(k)（k为1的个数）；
- ⚠️ goal = 0 是独立分支，不可与 goal > 0 统一处理，否则会错误计入含 1 的子数组；
- ? 边界安全：gaps 长度至少为 1，range(len(gaps) - goal) 自动处理 goal 过大（返回0）的情况。
该方法不仅正确性可严格数学归纳证明，且具备极佳的可扩展性——类似思路可迁移至「恰好 k 个不同元素的子数组」等结构化计数问题。
