LeetCode 2765. 最长交替子数组

目录

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解

---

一、题目

1、题目描述

给你一个下标从?0?开始的整数数组?nums?。如果?nums?中长度为?m?的子数组?s?满足以下条件，我们称它是一个?交替子数组?：

• m?大于?1?。
• s1 = s0 + 1?。
• 下标从?0?开始的子数组?s?与数组?[s0, s1, s0, s1,...,s(m-1) % 2]?一样。也就是说，s1 - s0 = 1?，s2 - s1 = -1?，s3 - s2 = 1?，s4 - s3 = -1?，以此类推，直到?s[m - 1] - s[m - 2] = (-1)m?。

请你返回?nums?中所有?交替?子数组中，最长的长度，如果不存在交替子数组，请你返回?-1?。

子数组是一个数组中一段连续?非空?的元素序列。

2、接口描述

?

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        
    }
};

3、原题链接

2765. 最长交替子数组

---

二、解题报告

1、思路分析

一次遍历，直接模拟

对于交替子序列sub而言，要满足sub[0] + 1 = sub[1]

所以我们先找sub[0] 和 sub[1]，然后往后遍历，直到不满足交替，然后停止，维护序列长度最大值

2、复杂度

时间复杂度： O(N) 空间复杂度：O(1)

3、代码详解

?

class Solution {
public:
    int alternatingSubarray(vector<int>& nums) {
        int ret = -1 , n = nums.size() , i = 0;
        while(i < n - 1)
        {
            if(nums[i] + 1 != nums[i + 1]) {i++; continue;}
            int st = i; i += 2;
            while(i < n && nums[i] == nums[st] + (i - st) % 2) i++;
            ret = max(ret , i-- - st);
        }

        return ret;
    }
};