本文深入剖析二进制数组中和为 goal 的非空连续子数组计数问题，指出朴素双指针的逻辑缺陷，并基于“1的位置间隙建模”提出严谨、线性时间的最优解法，特别处理 goal = 0 等边界情形。
本文深入剖析二进制数组中和为 `goal` 的非空连续子数组计数问题，指出朴素双指针的逻辑缺陷，并基于“1的位置间隙建模”提出严谨、线性时间的最优解法，特别处理 `goal = 0` 等边界情形。
在 leetcode 第 930 题 Binary Subarrays With Sum 中，给定仅含 0 和 1 的数组 nums 与目标整数 goal，要求返回和恰好等于 goal 的非空连续子数组个数。初看易联想到经典滑动窗口（双指针）解法，但题干隐含关键约束：数组元素非负（实为 0/1），且 goal 可为 0——这使得标准“收缩左边界直到 sum ≤ goal”的策略失效，尤其在全零数组等边缘场景下极易漏解。
原提问者实现的双指针逻辑存在根本性缺陷：当 sumSoFar == goal 时，仅单向扩展右指针或收缩左指针，却未考虑同一窗口内存在多个合法子数组起点与终点组合。例如对 nums = [0,0,0,0], goal = 0，所有长度 ≥1 的子数组均满足条件（共 10 个），但其算法因无法回溯探索不同 (i, j) 组合而仅统计部分结果（输出 10 而非期望的 15）。问题本质在于：当窗口和固定为 goal 时，左右边界的移动并非互斥，而是可独立选择的自由度。
核心洞见：将问题转化为“1 的间隙计数”
真正高效的解法不依赖动态调整窗口，而是进行结构化预处理：聚焦 1 的位置，将数组划分为若干由 1 分隔的“零区间”（gaps）。关键观察如下：
- 若 goal > 0，任一满足条件的子数组必须恰好包含 goal 个 1，且其左右边界必然落在包围这 goal 个 1 的相邻零区间内。
- 设第 k 个 1 前有 a 个连续 0（含该 1 自身位置），第 k+goal-1 个 1 后有 b 个连续 0，则以这 goal 个 1 为核心的所有合法子数组数量为 a × b（左端点有 a 种选法，右端点有 b 种选法）。
- 因此，我们可构建 gaps 数组：gaps[i] 表示第 i 个 1 到前一个 1（或数组起点）的距离 + 1（即包含当前 1 的左侧零段长度）。末尾额外追加一段尾部零区间长度 + 1。
例如 nums = [0,0,0,0,1,0,1,0,0,1,0], goal = 2：
- 1 的索引为 [4,6,9]
- gaps = [4-0+1, 6-4+1, 9-6+1, 11-9+1] = [5,3,4,3]（注：实际实现中需统一偏移，见下方代码）
- 对 goal=2，需计算 gaps[0]*gaps[2] + gaps[1]*gaps[3] = 5×4 + 3×3 = 20 + 9 = 29（此处为示意，精确构造见代码）
特殊处理：goal == 0
当 goal = 0 时，所有合法子数组均由连续 0 构成。若某段连续 0 长度为 L，则其贡献的子数组数为 L*(L+1)/2（即长度为 1 至 L 的所有子数组数量和）。这正是三角形数公式，可直接计算。
完整实现与说明
class Solution: def numSubarraysWithSum(self, nums, goal): # 步骤1：构建gaps数组——记录每个'1'与其前一个'1'（或数组起始）之间的距离+1 # gaps[0] = 第一个1的位置 + 1（即从索引0到第一个1含多少个元素） # gaps[i] (i>0) = 第i个1与第i-1个1之间的距离（含第i个1） # 最后一个gap = 数组长度 - 最后一个1的索引（即尾部0的个数 + 1） gaps = [] last_one_idx = -1 # 记录上一个1的索引，初始设为-1便于计算第一个1 for i, x in enumerate(nums): if x == 1: gaps.append(i - last_one_idx) # 当前1与上一个1的距离（含当前1） last_one_idx = i # 添加尾部gap：从最后一个1到数组末尾的长度 + 1（因为最后一个1已计入前面gap） gaps.append(len(nums) - last_one_idx) if goal == 0: # 对每个gap（代表一段连续0的长度），计算其内部子数组数：L*(L-1)//2 # 注意：gaps[i] 是包含1的区间长度，但goal=0时我们只关心纯0段 # 实际上，上述gaps构造中，每个gap减1才是纯0段长度（除首尾可能） # 更稳健做法：单独提取纯0段长度 total = 0 zeros = 0 for x in nums: if x == 0: zeros += 1 else: total += zeros * (zeros + 1) // 2 zeros = 0 total += zeros * (zeros + 1) // 2 return total else: # goal >= 1：gaps[i] 表示第i个1左侧（含自身）的“有效起点数” # 我们需要取 gaps[i] * gaps[i+goal]，其中 i+goal < len(gaps) # 因为第i个1到第i+goal-1个1构成goal个1，其左侧有gaps[i]种起点，右侧有gaps[i+goal]种终点 if len(gaps) <= goal: return 0 return sum(gaps[i] * gaps[i + goal] for i in range(len(gaps) - goal))✅ 关键修正说明：原始答案中的 gaps 构造存在索引歧义。本实现采用更清晰的定义——gaps[i] 严格表示第 i 个 1 所在位置及其左侧连续 0 的总跨度（即从上一个 1 后一位到当前 1 的元素个数）。这样 gaps[i] * gaps[i+goal] 直观对应以第 i 至 i+goal-1 个 1 为核心的子数组数量。
注意事项与总结
- 时间复杂度：O(n)，仅需两次遍历（构建 gaps 和求和）；空间复杂度：O(k)，k 为 1 的个数，最坏 O(n)。
- 避免常见错误：
- 不要尝试用普通双指针处理 goal=0，它无法枚举所有零子数组组合；
- gaps 数组的构造必须保证语义一致，推荐使用“1 的位置差”方式，而非模糊的“零个数+1”；
- 当 goal > 1 的个数时，直接返回 0（len(gaps)
- 本质思想：将子数组计数问题升维为组合数学问题——通过定位关键元素（1）并量化其周围自由度（0 的分布），将连续性约束转化为离散乘积运算，从而规避动态窗口的路径依赖缺陷。
此方法不仅正确覆盖所有边缘案例（如全零、单 1、goal=0），更体现了算法设计中“问题转化”与“结构洞察”的核心能力。