问题分析题目要求给定一个整数数组nums和一个整数threshold寻找最长的奇偶子数组。子数组需满足以下条件子数组的第一个元素是偶数。子数组中的元素奇偶性交替即nums[i] % 2 ! nums[i1] % 2。子数组中的每个元素都不大于threshold。核心约束在于子数组必须同时满足奇偶性交替和元素值上限两个条件。一旦某个元素不满足任一条件当前子数组的连续性即被破坏需要从新的位置开始寻找。算法设计1. 滑动窗口 (双指针)这是最直观且高效的解法。使用两个指针left和right来定义当前考察的子数组窗口[left, right]。我们不断尝试扩展右边界right并在每次扩展后检查新加入的元素nums[right]是否破坏了子数组的合法性。如果破坏则收缩左边界left至right的位置并重新开始构建窗口。关键点合法性检查对于窗口[left, right]需要检查nums[right]是否满足nums[right] threshold如果right left则它是窗口的第一个元素必须是偶数。如果right left则nums[right]的奇偶性必须与nums[right-1]相反。窗口维护当nums[right]合法时扩展窗口 (right)不合法时将窗口重置 (left right, right left)但需注意如果nums[right]本身不满足条件1则left和right都应跳到下一位 (left right 1, right left)。2. 模拟 (一次遍历)滑动窗口的变体可以简化为一次遍历。我们维护一个当前有效子数组的长度currentLength和全局最大长度maxLength。遍历数组根据当前元素nums[i]与上一个元素nums[i-1]的关系以及阈值条件决定是延续当前子数组还是开始一个新的子数组。状态判断逻辑如果nums[i] threshold当前元素绝对非法currentLength重置为0。否则如果currentLength 0说明我们正在尝试开始一个新的子数组。此时需要nums[i] % 2 0才能成功开始currentLength 1否则保持为0。否则 (currentLength 0)说明我们处于一个有效的子数组中。此时需要检查奇偶交替条件nums[i] % 2 ! nums[i-1] % 2。如果满足currentLength否则说明奇偶性没有交替但nums[i]本身可能可以作为下一个子数组的起点如果它是偶数因此currentLength应重置为(nums[i] % 2 0) ? 1 : 0。C 代码实现方案一滑动窗口 (双指针)class Solution { public: int longestAlternatingSubarray(vectorint nums, int threshold) { int n nums.size(); int maxLen 0; int left 0, right 0; while (right n) { // 条件1元素值不超过阈值 if (nums[right] threshold) { // 当前元素非法左右指针都跳到下一个位置 left right 1; right left; continue; } // 条件2 3奇偶性检查 if (right left) { // 子数组第一个元素必须是偶数 if (nums[right] % 2 ! 0) { left right 1; right left; continue; } } else { // 后续元素必须奇偶交替 if (nums[right] % 2 nums[right - 1] % 2) { // 不满足交替从right开始新的窗口 left right; // right指针不动下一轮循环会以right为left重新判断 continue; } } // 当前窗口 [left, right] 合法更新最大长度 maxLen max(maxLen, right - left 1); right; // 尝试扩展右边界 } return maxLen; } };代码解析left和right指针初始化为0。外层while循环控制右指针right遍历数组。内部分三步检查合法性首先检查阈值条件nums[right] threshold。如果违反则left和right都移动到right1彻底跳过这个非法元素 。然后检查是否是窗口起点 (right left)。如果是则要求nums[right]为偶数否则重置窗口 。最后检查奇偶交替性 (nums[right] % 2 nums[right-1] % 2)。如果相同说明交替性被破坏将left移动到right准备以当前位置为起点构建新窗口 。只有当所有条件都满足时才计算当前窗口长度并更新maxLen然后right继续扩展。方案二模拟 (一次遍历)class Solution { public: int longestAlternatingSubarray(vectorint nums, int threshold) { int maxLen 0; int currentLen 0; int n nums.size(); for (int i 0; i n; i) { if (nums[i] threshold) { // 违反阈值条件当前子数组终结 currentLen 0; } else if (currentLen 0) { // 尝试开始一个新的子数组首元素必须为偶数 currentLen (nums[i] % 2 0) ? 1 : 0; } else { // 已在子数组中检查奇偶是否交替 if (nums[i] % 2 ! nums[i - 1] % 2) { currentLen; } else { // 没有交替当前元素可能作为新子数组的起点 currentLen (nums[i] % 2 0) ? 1 : 0; } } maxLen max(maxLen, currentLen); } return maxLen; } };代码解析currentLen记录以当前位置i结尾的、满足条件的最长子数组长度。maxLen记录全局最大值。遍历中的三个分支对应三种状态元素值超标直接清零currentLen因为任何包含该元素的子数组都不合法 。当前无有效子数组(currentLen 0)尝试以nums[i]作为新起点。只有当它是偶数时才能成功开启一个长度为1的子数组 。已有有效子数组(currentLen 0)检查奇偶交替性。如果交替长度加1如果不交替说明连续性中断。但nums[i]本身如果为偶数它可以立即作为下一个子数组的起点长度为1否则长度归零 。每次循环后更新maxLen。复杂度与方案对比特性滑动窗口 (双指针)模拟 (一次遍历)时间复杂度O(n)每个元素最多被访问两次 (左指针和右指针) 。O(n)严格一次遍历。空间复杂度O(1)只使用了常数个额外变量。O(1)只使用了常数个额外变量。核心思想显式地维护一个合法的窗口[left, right]通过移动左右指针来动态调整窗口。隐式地维护当前有效子数组的长度currentLen根据规则进行状态转移。代码逻辑指针移动的逻辑稍显复杂需要仔细处理窗口重置的边界条件。逻辑更简洁类似于动态规划的状态机容易理解和实现。推荐度直观展示了“窗口”概念适合理解滑动窗口算法。更优。代码更简洁运行效率相同是本题更常见的解法 。示例演示以nums [3, 2, 5, 4],threshold 5为例演示模拟法的过程inums[i]条件判断currentLen 变化maxLen033 5?否。currentLen0且3%2!0所以currentLen0。00122 5?否。currentLen0且2%20所以currentLen1。11255 5?否。currentLen0。检查奇偶5%21,2%20交替成立currentLen。22344 5?否。currentLen0。检查奇偶4%20,5%21交替成立currentLen。33最终找到的最长子数组为[2, 5, 4]长度为3 。参考来源LeetCode解法汇总2760. 最长奇偶子数组Leetcode—2760.最长奇偶子数组【简单】LeetCode 2760. 最长奇偶子数组模拟使用一个变量记录状态2760. 最长奇偶子数组 : 抽丝剥茧图解双指针做法正确性leetcode做题笔记2760. 最长奇偶子数组【每日一题】 2024年1月汇编
