【每日一题】最长交替子数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】最长交替子数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【双层循环】【单层循环】【数组】【2024-01-23】

题目来源

2765. 最长交替子数组

【每日一题】最长交替子数组,LeetCode每日一题,双层循环,单层循环,数组,2024-01-23

解题思路

两个方法，一个是双层循环，一个是单层循环。

方法一：双层循环

思路

第一层枚举子数组的起点，第二层从起点的下一个元素开始枚举，判断接下来的字符是否满足交替子数组的条件。如是则更新长度，否则调出内层循环。

算法

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int res = -1;
        int n = nums.size();
        for (int firstIndex = 0; firstIndex < n; firstIndex++) {
            for (int i = firstIndex + 1; i < n; i++) {
                int length = i - firstIndex + 1;
                if (nums[i] - nums[firstIndex] == (length - 1) % 2) {
                    res = max(res, length);
                } else {
                    break;
                }
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度： $O(n^2)$ ， $n$ 为数组 nums 的长度。

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

方法二：单层循环

思路

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

算法

class Solution {
public:
    int alternatingSubarray(vector<int> &nums) {
        int ans = -1;
        int i = 0, n = nums.size();
        while (i < n - 1) {
            if (nums[i + 1] - nums[i] != 1) {
                i++; // 直接跳过
                continue;
            }
            int i0 = i; // 记录这一组的开始位置
            i += 2; // i 和 i+1 已经满足要求，从 i+2 开始判断
            while (i < n && nums[i] == nums[i0] + (i - i0) % 2) {
                i++;
            }
            // 从 i0 到 i-1 是满足题目要求的（并且无法再延长的）子数组
            ans = max(ans, i - i0);
            i--;
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 为数组 nums 的长度。

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