当前位置：首页 > news >正文

LeetCode 930：和相同的二元子数组 | 前缀和与哈希表

news 2026/5/24 1:00:45

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 count

Python 实现（计数）

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("所有测试用例通过！")