LeetCode 题解工作台
和相同的二元子数组
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。 子数组 是数组的一段连续部分。 示例 1： 输入： nums = [1,0,1,0,1], goal = 2 输出： 4 解释： 有 4 个满足题目要求的子数组：[1,0,1]、[1,0,…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们可以用数组或哈希表 记录每个前缀和出现的次数，其中 表示前缀和为 的子数组个数。初始时 $cnt[0] = 1$。 接下来我们遍历数组 `nums`，用变量 维护当前的前缀和，对于每个 ，我们可以计算出 $s - goal$ 出现的次数，即为以当前位置结尾的满足条件的子数组个数，累加到答案中。然后我们将 的计数值加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
子数组 是数组的一段连续部分。
示例 1：
输入：nums = [1,0,1,0,1], goal = 2 输出：4 解释： 有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
示例 2：
输入：nums = [0,0,0,0,0], goal = 0 输出：15
提示：
1 <= nums.length <= 3 * 104nums[i]不是0就是10 <= goal <= nums.length
解题思路
方法一：数组或哈希表 + 前缀和
我们可以用数组或哈希表 记录每个前缀和出现的次数，其中 表示前缀和为 的子数组个数。初始时 。
接下来我们遍历数组 nums，用变量 维护当前的前缀和，对于每个 ，我们可以计算出 出现的次数，即为以当前位置结尾的满足条件的子数组个数，累加到答案中。然后我们将 的计数值加 。
最终的答案即为满足条件的子数组个数。
时间复杂度 ，空间复杂度 。其中 为数组 nums 的长度。
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
cnt = Counter({0: 1})
ans = s = 0
for v in nums:
s += v
ans += cnt[s - goal]
cnt[s] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Checks if you can optimize counting subarrays without nested loops.
- question_mark
May ask why sliding window alone fails when zeros exist.
- question_mark
Looks for clear explanation of prefix sum mapping to goal counts.
常见陷阱
外企场景- error
Forgetting to initialize prefix sum count map with 0 sum seen once.
- error
Updating hash map before counting current subarrays can undercount.
- error
Misinterpreting zeros and ones leads to missing valid subarrays.
进阶变体
外企场景- arrow_right_alt
Count subarrays with sum less than or equal to goal.
- arrow_right_alt
Handle arrays with arbitrary integers, not just binary.
- arrow_right_alt
Return all subarrays instead of counting them.