LeetCode 题解工作台
交替子数组计数
给你一个 二进制数组 nums 。 如果一个 子数组 中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。 返回数组 nums 中交替子数组的数量。 示例 1： 输入： nums = [0,1,1,1] 输出： 5 解释： 以下子数组是交替子数组： [0] 、 [1]…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们可以枚举以每个位置结尾的子数组，计算满足条件的子数组的数量，累加所有位置的满足条件的子数组的数量即可。 具体地，我们定义变量 表示以元素 结尾的满足条件的子数组的数量，初始时我们将 置为 ，表示以第一个元素结尾的满足条件的子数组的数量为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个二进制数组 nums 。
如果一个子数组中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。
返回数组 nums 中交替子数组的数量。
示例 1：
输入： nums = [0,1,1,1]
输出： 5
解释：
以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。
示例 2：
输入： nums = [1,0,1,0]
输出： 10
解释：
数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。
提示：
1 <= nums.length <= 105nums[i]不是0就是1。
解题思路
方法一：枚举
我们可以枚举以每个位置结尾的子数组，计算满足条件的子数组的数量，累加所有位置的满足条件的子数组的数量即可。
具体地，我们定义变量 表示以元素 结尾的满足条件的子数组的数量，初始时我们将 置为 ，表示以第一个元素结尾的满足条件的子数组的数量为 。
接下来，我们从第二个元素开始遍历数组，对于每个位置 ，我们根据 和 的关系更新 的值：
- 如果 ，则 的值增加 ，即 ；
- 如果 ，则 的值重置为 ，即 。
然后，我们将 的值累加到答案中，继续遍历数组的下一个位置，直到遍历完整个数组。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def countAlternatingSubarrays(self, nums: List[int]) -> int:
ans = s = 1
for a, b in pairwise(nums):
s = s + 1 if a != b else 1
ans += s
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for a single traversal or DP solution, where n is nums.length. Space complexity is O(n) for DP or O(1) for linear counting with a rolling variable. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask for a solution that handles large arrays efficiently.
- question_mark
Check if the candidate recognizes overlapping subarrays and can optimize counting.
- question_mark
Probe understanding of array patterns and use of cumulative math formulas.
常见陷阱
外企场景- error
Counting only subarrays of length 2 and missing longer alternating sequences.
- error
Resetting counts incorrectly when consecutive elements are equal, undercounting subarrays.
- error
Using nested loops, leading to timeouts for arrays near length 10^5.
进阶变体
外企场景- arrow_right_alt
Count alternating subarrays in ternary arrays instead of binary arrays.
- arrow_right_alt
Return the length of the longest alternating subarray instead of total count.
- arrow_right_alt
Count alternating subarrays that start with 1 only, skipping those starting with 0.