LeetCode 2765. 最长瓜代子数组分析与解题思绪

LeetCode 2765. 最长瓜代子数组分析与解题思绪

在本篇博客中，我们将深入分析 LeetCode 上的一道风趣标题 —— 2765. 最长瓜代子数组。我们将通过标题明白、解题思绪、代码实现以及示例分析，全面把握这道标题标办理方法。
标题形貌

给定一个下标从 0 开始的整数数组 nums，如果数组中长度为 m 的子数组 s 满足以下条件，我们称其为一个 瓜代子数组：

• m 大于 1。
  
• s1 = s0 + 1。
  
• 子数组 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-1)。
  

请你返回 nums 中全部瓜代子数组中，最长的长度。如果不存在瓜代子数组，请返回 -1。
注意：

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

示例

示例 1：

1. 输入：nums = [2,3,4,3,4]
3. 输出：4
4. 解释：交替子数组有 [2,3]，[3,4]，[3,4,3] 和 [3,4,3,4]。最长的子数组为 [3,4,3,4]，长度为 4。

复制代码

示例 2：

1. 输入：nums = [4,5,6]
3. 输出：2
4. 解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2。

复制代码

提示

• 2 <= nums.length <= 100
  
• 1 <= nums <= 10^4
  

解题思绪

为了找到数组中最长的瓜代子数组，我们必要按照标题界说的条件举行查抄。详细来说：

• 子数组长度大于1：我们只必要思量长度至少为2的子数组。
  
• 相邻元素关系：第一个元素与第二个元素之间的差必须为1，即 s1 = s0 + 1。
  
• 瓜代关系：之后的元素必要瓜代地增减，即 s2 = s1 - 1，s3 = s2 + 1，以此类推。
  

基于上述条件，我们可以采取滑动窗口的方法，遍历数组，找到满足条件的最宗子数组。
详细步调

• 初始化答案 ans 为 -1，表现尚未找到满足条件的子数组。
  
• 利用指针 i 遍历数组，从第一个元素开始。
  
• 对于每一个位置 i，查抄 nums[i+1] - nums 是否便是1。如果不便是1，则继续移动指针。
  
• 如果满足 nums[i+1] - nums == 1，则记载当前起始位置 i0。
  
• 然后，开始查抄后续元素是否符合瓜代关系：
  
  
  
  • 第三个元素 nums[i+2] 应该便是 nums（即 nums[i+2] == nums）。
    
  • 第四个元素 nums[i+3] 应该便是 nums[i+1]，以此类推。
    
  
  
• 连续扩展子数组长度，直到不满足瓜代关系。
  
• 更新 ans 为当前找到的子数组长度与之前记载的最大值之间的较大者。
  
• 重复上述过程，直到遍历完备个数组。
  
• 末了返回 ans。
  

代码实现

以下是基于上述思绪的 Python 代码实现：

1. class Solution:
2.     def alternatingSubarray(self, nums: List[int]) -> int:
3.         ans = -1
4.         i, n = 0, len(nums)
5.         while i < n - 1:
6.             # 检查当前和下一个元素是否满足差为1
7.             if nums[i + 1] - nums[i] != 1:
8.                 i += 1
9.                 continue
10.             # 记录当前起始位置
11.             i0 = i
12.             i += 2
13.             # 检查后续元素是否满足交替关系
14.             while i < n and nums[i - 2] == nums[i]:
15.                 i += 1
16.             # 更新答案
17.             ans = max(ans, i - i0)
18.             # 回退一位，以防漏掉可能的子数组
19.             i -= 1
20.         return ans

复制代码

代码分析

• 初始化：
  
  
  
  • ans = -1：用于记载最长的瓜代子数组长度，初始设为 -1 表现尚未找到。
    
  • i, n = 0, len(nums)：i 为当前遍历的索引，n 为数组长度。
    
  
  
• 主循环：
  
  
  
  • while i < n - 1：遍历数组，确保至少有两个元素可以比力。
    
  • if nums[i + 1] - nums != 1：查抄当前元素与下一个元素的差是否为1，不满足则移动指针 i。
    
  
  
• 找到大概的瓜代子数组出发点：
  
  
  
  • i0 = i：记载子数组的起始位置。
    
  • i += 2：跳过下一个元素，预备查抄更长的子数组。
    
  
  
• 查抄瓜代关系：
  
  
  
  • while i < n and nums[i - 2] == nums：查抄当前元素是否便是起始位置的元素，以维持瓜代关系。
    
  • i += 1：如果满足条件，继续扩展子数组长度。
    
  
  
• 更新答案：
  
  
  
  • ans = max(ans, i - i0)：更新最宗子数组长度。
    
  • i -= 1：回退一位，防止遗漏匿伏的子数组。
    
  
  
• 返回效果：
  
  
  
  • return ans：返回找到的最长瓜代子数组长度，如果没有则返回 -1。
    
  
  

示例分析

让我们通过示例来更好地明白算法的实行过程。
示例 1

1. 输入：nums = [2,3,4,3,4]

复制代码

步调：

• i = 0：
  
  
  
  • nums[1] - nums[0] = 3 - 2 = 1，满足条件。
    
  • i0 = 0，i = 2。
    
  • 查抄 nums[0] == nums[2] 即 2 == 4，不满足，制止扩展。
    
  • 更新 ans = max(-1, 2 - 0) = 2。
    
  
  
• i = 1：
  
  
  
  • nums[2] - nums[1] = 4 - 3 = 1，满足条件。
    
  • i0 = 1，i = 3。
    
  • 查抄 nums[1] == nums[3] 即 3 == 3，满足，i = 4。
    
  • 查抄 nums[2] == nums[4] 即 4 == 4，满足，i = 5（超出范围）。
    
  • 更新 ans = max(2, 5 - 1) = 4。
    
  
  
• 遍历竣事，返回 ans = 4。
  

效果：4
示例 2

1. 输入：nums = [4,5,6]

复制代码

步调：

• i = 0：
  
  
  
  • nums[1] - nums[0] = 5 - 4 = 1，满足条件。
    
  • i0 = 0，i = 2。
    
  • 查抄 nums[0] == nums[2] 即 4 == 6，不满足，制止扩展。
    
  • 更新 ans = max(-1, 2 - 0) = 2。
    
  
  
• i = 1：
  
  
  
  • nums[2] - nums[1] = 6 - 5 = 1，满足条件。
    
  • i0 = 1，i = 3（超出范围）。
    
  • 更新 ans = max(2, 3 - 1) = 2。
    
  
  
• 遍历竣事，返回 ans = 2。
  

效果：2