# LeetCode 2760: 最长奇偶子数组

LeetCode 2760: 最长奇偶子数组

问题形貌

给定一个整数数组 nums 和一个整数 threshold，你必要从 nums 的子数组中找出最长的符合以下条件的子数组&#xff1
a;

• 子数组的第一个元素是偶数，且小于等于 threshold。
  
• 子数组内的元素瓜代出现，即相邻元素的奇偶性差别。
  
• 子数组中的每个元素都必须小于等于 threshold。
  

请返回满意上述条件的最宗子数组的长度。
示例

[size=3

]示例 1


输入&#xff1
a;

1. nums &#61
2. ; [3
4. , 2, 5, 4]
5. threshold &#61
6. ; 5

复制代码

输出&#xff1
a;

1. 3

复制代码

解释&#xff1
a;
选择从 l &#61
; 1
到 r &#61
; 3

的子数组 [2, 5, 4]，满意所有条件&#xff1
a;

• 2 是偶数，符合第一个条件&#xff1
  b;
  
• 2 和 5 是瓜代奇偶，符合第二个条件&#xff1
  b;
  
• 2, 5, 4 都小于等于 threshold。
  

因此，最长的满意条件的子数组长度为 3

。
[size=3

]示例 2

输入&#xff1
a;

1. nums &#61
2. ; [1
3. , 2]
4. threshold &#61
5. ; 2

复制代码

输出&#xff1
a;

1. 1

复制代码

解释&#xff1
a;
选择子数组 [2]，它满意所有条件&#xff1
a;

• 2 是偶数&#xff1
  b;
  
• 子数组只有一个元素，没有瓜代的要求&#xff1
  b;
  
• 2 小于等于 threshold。
  

因此，最宗子数组的长度为 1
。
[size=3

]示例 3



输入&#xff1
a;

1. nums &#61
2. ; [2, 3
4. , 4, 5]threshold &#61
5. ; 4

复制代码

输出&#xff1
a;

1. 3

复制代码

解释&#xff1
a;
选择从 l &#61
; 0 到 r &#61
; 2 的子数组 [2, 3

, 4]，满意所有条件&#xff1
a;

• 2 是偶数&#xff1
  b;
  
• 2 和 3
  
  瓜代奇偶，3
  
  和 4 瓜代奇偶&#xff1
  b;
  
• 2, 3
  
  , 4 都小于等于 threshold。
  

因此，最宗子数组的长度为 3

。
思路分析

我们可以使用 双指针法 来办理这个问题。
[size=3

]步骤&#xff1
a;

[list=1
]

外层循环&#xff1
a;从数组的每个偶数开始，作为埋伏的子数组的出发点。

内层循环&#xff1
a;从当前偶数开始，逐个检查后续的元素&#xff1
a;

• 如果当前元素小于等于 threshold 且奇偶性瓜代，则继承扩展子数组&#xff1
  b;
  
• 如果出现不满意条件的元素，则竣事当前子数组的扩展。
  

更新最大子数组长度&#xff1
a;在内层循环竣事后，更新最宗子数组的长度。
[size=3

]时间复杂度&#xff1
a;

• 外层循环遍历 nums，时间复杂度为 O(n)。
  
• 内层循环遍历每个埋伏子数组，最坏情况下每个元素会被遍历一次，总时间复杂度为 O(n²)。
  

由于 n 的最大值为 1
00，O(n²) 的复杂度是可以担当的。
代码实现

1. class Solution:    def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:        res, n &#61
2. ; 0, len(nums)        # 外层循环，遍历每个偶数且小于等于 threshold 的元素        for i in range(n):            if nums[i] % 2 !&#61
3. ; 0 or nums[i] > threshold:                 continue            else:                a &#61
4. ; 1
5.   # 子数组的初始长度为 1
6.                 for j in range(i &#43
8. ; 1
9. , n):                    # 判断是否是瓜代的子数组且小于等于 threshold                    if nums[j] <&#61
10. ; threshold and nums[j - 1
11. ] % 2 !&#61
12. ; nums[j] % 2:                        a &#43
14. ;&#61
15. ; 1
16.                     else:                        break  # 不满意条件，退出内层循环                res &#61
17. ; max(res, a)  # 更新最大长度        return res

复制代码

解释

• 外层循环&#xff1
  a;我们从每一个偶数且小于等于 threshold 的元素开始，逐个考虑它作为子数组的出发点。
  
• 内层循环&#xff1
  a;对于每一个子数组，我们检查是否满意瓜代条件以及每个元素是否小于等于 threshold。如果满意条件，则继承扩展子数组&#xff1
  b;否则，停止扩展。
  
• 更新最大值&#xff1
  a;每次竣事内层循环后，我们更新当前找到的最长瓜代子数组的长度。
  

边界情况

[list=1
]

数组只有一个元素&#xff1
a;

• 如果该元素是偶数且小于等于 threshold，则返回 1
  。
  
• 如果该元素不符合条件，则返回 0。
  

所有元素都不满意条件&#xff1
a;

• 如果没有任何偶数满意条件，返回 0。
  

数组元素全部类似&#xff1
a;

• 如果所有元素都是偶数而且小于等于 threshold，且数组长度大于 1
  ，则返回 1
  （因为没有瓜代的子数组）。
  

总结

本题的关键是使用双指针或滑动窗口来探求最长的瓜代子数组，保证每个元素符合条件并满意瓜代奇偶性。通过适当的内外层循环判断，可以高效地找到答案。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao1
23

.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。