LeetCode 930：和相同的二元子数组 | 前缀和与哈希表
引言
和相同的二元子数组（Binary Subarrays With Sum）是 LeetCode 第 930 题，难度为 Medium。题目要求在二元数组（元素只有 0 和 1）中找出子数组和等于 S 的数量。这道题与 LeetCode 560（和为 K 的子数组）非常相似，但因为数组是二元的，可以使用更高效的方法。
对于二元数组，我们可以使用"计数法"来优化：当 S 较大时，遍历所有子数组可能需要 O(n²) 时间；但使用哈希表方法仍然是 O(n)。另一种方法是使用"滑动窗口"，因为数组是二元的，可以更高效地处理。
问题分析
题目描述
给定一个二元数组 nums 和一个整数 S，计算有多少个子数组的元素和等于 S。
例如，输入 nums = [1,0,1,0,1]，S = 2，有 4 个子数组的和等于 2：
- [1,0,1]（索引 0-2）
- [1,0,1]（索引 2-4）
- [0,1,0,1]（索引 1-4）
- [1]（但这个和为 1，不是 2，所以只有前三个？）
实际上，正确答案是：
- [1,0,1]（索引 0-2）：1+0+1=2
- [1,0,1]（索引 2-4）：1+0+1=2
- [1,0,1,0,1]的和是3，不是2
问题特点
因为数组是二元的，元素只能是 0 或 1。这使得我们可以使用更高效的方法。但核心思路仍然是前缀和与哈希表。
解决方案
前缀和哈希表方法
def numSubarraysWithSum(nums, s): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num count += prefix_map.get(prefix_sum - s, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count这与 LeetCode 560 的解法完全相同。对于任意整数数组（包括二元数组），这个方法都适用。
计数方法（优化）
因为数组是二元的，我们可以使用更直接的方法。观察发现，对于子数组和为 S 的情况，子数组中必须恰好有 S 个 1。这 S 个 1 之间的 0 可以任意数量。
def numSubarraysWithSum_optimized(nums, s): def countAtMost(k): if k < 0: return 0 result = 0 left = 0 count = 0 for right in range(len(nums)): if nums[right] == 1: count += 1 while count > k: if nums[left] == 1: count -= 1 left += 1 result += right - left + 1 return result return countAtMost(s) - countAtMost(s - 1)这个方法计算"至多 s 个 1"的子数组数量减去"至多 s-1 个 1"的子数组数量，得到恰好 s 个 1 的子数组数量。
算法正确性证明
计数方法的正确性
对于"至多 s 个 1"的子数组数量，使用滑动窗口方法计算。每次扩展右边界，统计以当前右边界结尾的满足条件的子数组数量（right - left + 1）。然后收缩左边界直到窗口内 1 的数量不超过 s。
减法原理：恰好 s 个 1 的子数组 = 至多 s 个 1 的子数组 - 至多 s-1 个 1 的子数组。
复杂度分析
哈希表方法
时间复杂度：O(n)
空间复杂度：O(n)
计数方法
时间复杂度：O(n)（两次遍历）
空间复杂度：O(1)
代码实现
Python 实现（哈希表）
def numSubarraysWithSum(nums, s): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num count += prefix_map.get(prefix_sum - s, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return countPython 实现（计数）
def numSubarraysWithSum_count(nums, s): def countAtMost(k): if k < 0: return 0 result = 0 left = 0 count = 0 for right in range(len(nums)): if nums[right] == 1: count += 1 while count > k: if nums[left] == 1: count -= 1 left += 1 result += right - left + 1 return result return countAtMost(s) - countAtMost(s - 1)边界情况处理
S = 0
当 S = 0 时，需要统计和为 0 的子数组数量，即没有 1 的子数组。计数方法中的 countAtMost(-1) 会返回 0，countAtMost(0) 会正确计算没有 1 的子数组数量。
全 0 数组
当数组全为 0 时，子数组和都是 0。如果 S = 0，子数组数量是 n*(n+1)/2；如果 S > 0，子数组数量是 0。两种方法都能正确处理。
全 1 数组
当数组全为 1 时，子数组和等于子数组长度。计数方法使用滑动窗口，正确统计恰好 s 个 1 的子数组数量。
测试用例
def test_num_subarrays_with_sum(): assert numSubarraysWithSum([1,0,1,0,1], 2) == 4 assert numSubarraysWithSum([1,0,1,0,1], 0) == 4 assert numSubarraysWithSum([0,0,0,0,0], 0) == 15 assert numSubarraysWithSum([1,1,1,1], 2) == 3 assert numSubarraysWithSum([1], 0) == 0 assert numSubarraysWithSum([0], 0) == 1 assert numSubarraysWithSum([], 0) == 1 print("所有测试用例通过！")总结
和相同的二元子数组问题展示了两种方法：通用的前缀和哈希表方法和针对二元数组优化的计数方法。两种方法都是 O(n) 时间复杂度，但计数方法空间复杂度更优（O(1) vs O(n)）。
对于二元数组，计数方法利用了"恰好 s 个 1"的特性，通过计算"至多 s 个"和"至多 s-1 个"的差来得到精确答案。这种转换思路在处理"恰好"问题时很有用。
