LeetCode 题解工作台
最长奇偶子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。 请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 且满足以下条件的 最长子数组 ： nums[l] % 2 == 0 对于范围 [l, r - 1] 内的所有下标 i ， nums[i] % 2 …
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 滑动窗口（状态滚动更新）
答案摘要
我们在 范围内枚举所有 ，如果 满足 $nums[l] \bmod 2 = 0$ 并且 $nums[l] \leq threshold$，那么我们就从 开始，查找第一个不满足条件的 ，那么此时以 作为左端点的最长奇偶子数组的长度为 $r - l$，取所有 $r - l$ 的最大值作为答案即可。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。
请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 <= l <= r < nums.length) 且满足以下条件的 最长子数组 ：
nums[l] % 2 == 0- 对于范围
[l, r - 1]内的所有下标i，nums[i] % 2 != nums[i + 1] % 2 - 对于范围
[l, r]内的所有下标i，nums[i] <= threshold
以整数形式返回满足题目要求的最长子数组的长度。
注意：子数组 是数组中的一个连续非空元素序列。
示例 1：
输入：nums = [3,2,5,4], threshold = 5 输出：3 解释：在这个示例中，我们选择从 l = 1 开始、到 r = 3 结束的子数组 => [2,5,4] ，满足上述条件。 因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。
示例 2：
输入：nums = [1,2], threshold = 2 输出：1 解释： 在这个示例中，我们选择从 l = 1 开始、到 r = 1 结束的子数组 => [2] 。 该子数组满足上述全部条件。可以证明 1 是满足题目要求的最大长度。
示例 3：
输入：nums = [2,3,4,5], threshold = 4 输出：3 解释： 在这个示例中，我们选择从 l = 0 开始、到 r = 2 结束的子数组 => [2,3,4] 。 该子数组满足上述全部条件。 因此，答案就是这个子数组的长度 3 。可以证明 3 是满足题目要求的最大长度。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 1001 <= threshold <= 100
解题思路
方法一：枚举
我们在 范围内枚举所有 ，如果 满足 并且 ，那么我们就从 开始，查找第一个不满足条件的 ，那么此时以 作为左端点的最长奇偶子数组的长度为 ，取所有 的最大值作为答案即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:
ans, n = 0, len(nums)
for l in range(n):
if nums[l] % 2 == 0 and nums[l] <= threshold:
r = l + 1
while r < n and nums[r] % 2 != nums[r - 1] % 2 and nums[r] <= threshold:
r += 1
ans = max(ans, r - l)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) because each element is visited at most twice by the sliding window. Space complexity is O(1) as no additional arrays or structures are required beyond pointers and counters. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
They may hint at optimizing brute force by using a sliding window.
- question_mark
Watch for questions about handling consecutive numbers with the same parity.
- question_mark
Expect discussion on early stopping when elements exceed the threshold.
常见陷阱
外企场景- error
Forgetting to check the threshold for every element.
- error
Not correctly resetting the window when parity alternation fails.
- error
Counting subarrays that partially violate the alternating pattern.
进阶变体
外企场景- arrow_right_alt
Longest odd-even subarray ignoring threshold constraints.
- arrow_right_alt
Maximum length subarray with alternating parity and a minimum value requirement.
- arrow_right_alt
Subarray with alternating even-odd elements and sum below a given target.