LeetCode二进制子数组和问题：滑动窗解法的核心逻辑疑问

先明确核心误解：你搞错了cnt(S)函数的作用——它不是计算和等于S的子数组数量，而是计算所有和≤S的非空子数组的总数。

拆解cnt(S)的逻辑 #

cnt函数用滑动窗口维护了一个区间[l, r]，保证这个区间内的子数组和始终≤S。每次右指针r移动后，累加r-l+1的原因是：以当前r为结尾的、满足和≤S的子数组，一共有r-l+1个（分别是[l,r]、[l+1,r]、...、[r,r]）。把这些数量全部加起来，就得到了数组中所有和≤S的子数组总数。

为什么要用cnt(goal) - cnt(goal-1)？ #

我们的目标是找和恰好等于goal的子数组数量。而：

• cnt(goal) = 所有和≤goal的子数组数量（包含和为0、1、...、goal的）
• cnt(goal-1) = 所有和≤goal-1的子数组数量（包含和为0、1、...、goal-1的）

两者相减，就把所有和≤goal-1的子数组全部排除了，剩下的正好就是和恰好等于goal的子数组数量——这就是题目要求的答案。

直观例子验证 #

比如数组nums = [1,0,1]，目标goal=1：

• cnt(1)统计的和≤1的子数组：[1]、[1,0]、[0]、[0,1]、[1]，共5个
• cnt(0)统计的和≤0的子数组：[0]，共1个
• 两者相减5-1=4，正好是和为1的子数组数量：[1]、[1,0]、[0,1]、[1]

对应代码逻辑 #

主函数里的return cnt(nums, goal) - cnt(nums, goal-1)就是直接套用这个逻辑，通过两个范围统计的差值，精准得到目标结果。

内容的提问来源于stack exchange，提问作者Ramkrishna Sharma