高效求解二进制子数组和为指定目标值的个数——基于“零间隙”建模的线性解法

碧海醫心

发布时间：2026-02-19 15:39:00

931人浏览过

来源于php中文网

原创

高效求解二进制子数组和为指定目标值的个数——基于“零间隙”建模的线性解法

本文详解如何正确统计二进制数组中和恰好等于 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 构造逻辑如下：

Molica AI

一款聚合了多种AI工具的一站式创作平台

下载

遍历 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 → 正确。

注意事项总结：