【每日一题】最长奇偶子数组

文章目录

• Tag
• 题目来源
• 解题思路
• • 方法一：枚举
  • 方法二：一次遍历
• 其他语言
• • python3
• 写在最后

Tag

【一次遍历】【枚举】【数组】【2023-11-16】

题目来源

2760. 最长奇偶子数组

解题思路

方法一：枚举

本题有多种方法可以解决，最朴素的方法就是枚举所有的子数组，对枚举的所有子数组逐一判断是否是符合要求的奇偶数组，统计最大的奇偶数组长度即可。

该方法属于基础语法范畴，不再进行详细分析，具体请见代码。

实现代码

class Solution {public:bool isValid(vector<int>& nums, int l , int r, int threshold) {if (nums[l] % 2 != 0) {return false;}for (int i = l; i <= r; ++i) {if (nums[i] > threshold || (i + 1 <= r && nums[i] % 2 == nums[i+1] % 2)) {return false;}}return true;}int longestAlternatingSubarray(vector<int>& nums, int threshold) {int n = nums.size();int res = 0;for (int l = 0; l < n; ++l) {for (int r = l; r < n; ++r) {if (isValid(nums, l, r, threshold)) {res = max(res, r - l + 1);}}}return res;}};

复杂度分析

时间复杂度： O ( n3)O(n^3)O(n3)，$n$ 是数组 nums 的长度。

空间复杂度：$O(1)$。

方法二：一次遍历

本方法参考 教你一次性把代码写对！O(n) 分组循环（Python/Java/C++/Go/JS/Rust）。

我们可以先找到有效的开始位置 i，再从有效的开始位置向后找最长的有效子数组的长度，该方法的时间复杂度为 $O(n)$，因为 i 是一直增加的，不会重置也不会减少。

实现代码

class Solution {public:int longestAlternatingSubarray(vector<int>& nums, int threshold) {int n = nums.size(), res = 0;int i = 0;while (i < n) {if (nums[i] > threshold || nums[i] % 2) {++i;continue;}int start = i;// 子数组的开始++i;// 子数组开始位置已经满足，从下一个位置开始判断while (i < n && nums[i] <= threshold && nums[i] % 2 != nums[i-1] % 2) {++i;}// 从 start 到 i-1 是符合条件的子数组res = max(res, i - start);}return res;}};

以上代码，建议记住，尤其是用 if 来找符合子数组起点，一定会有读者想用 while 来实现，读者可以尝试一下，会遇到很多错误的，如果你最后将 while 语句调试通过了，欢迎评论区沟通交流，你很厉害！

记住的代码可以作为一个模板使用，用来解决 “数组会被分割成若干组，且每一组的判断/处理逻辑是一样的” 这一类问题。

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

其他语言

python3

class Solution:def longestAlternatingSubarray(self, nums: List[int], threshold: int) -> int:n = len(nums)res, i = 0, 0while i  threshold or nums[i] % 2:i += 1continuestart = ii += 1while i < n and nums[i] <= threshold and nums[i] % 2 != nums[i-1] % 2:i += 1res = max(res, i - start)return res

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个哦。