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：
输入：nums = [2,3,4,3,4]
输出：4
解释：交替子数组有 [2,3]，[3,4]，[3,4,3] 和 [3,4,3,4]。最长的子数组为 [3,4,3,4]，长度为 4。
示例 2：
输入：nums = [4,5,6]
输出：2
解释：[4,5] 和 [5,6] 是仅有的两个交替子数组。它们长度都为 2。
提示
2 <= nums.length <= 1001 <= nums[i] <= 10^4
解题思路
为了找到数组中最长的交替子数组，我们需要按照题目定义的条件进行检查。具体来说：
- 子数组长度大于1：我们只需要考虑长度至少为2的子数组。
- 相邻元素关系：第一个元素与第二个元素之间的差必须为1，即
s1 = s0 + 1。 - 交替关系：之后的元素需要交替地增减，即
s2 = s1 - 1，s3 = s2 + 1，以此类推。
基于上述条件，我们可以采用滑动窗口的方法，遍历数组，找到满足条件的最长子数组。
具体步骤
- 初始化答案
ans为-1，表示尚未找到满足条件的子数组。 - 使用指针
i遍历数组，从第一个元素开始。 - 对于每一个位置
i，检查nums[i+1] - nums[i]是否等于1。如果不等于1，则继续移动指针。 - 如果满足
nums[i+1] - nums[i] == 1，则记录当前起始位置i0。 - 然后，开始检查后续元素是否符合交替关系：
- 第三个元素
nums[i+2]应该等于nums[i]（即nums[i+2] == nums[i]）。 - 第四个元素
nums[i+3]应该等于nums[i+1]，以此类推。
- 第三个元素
- 持续扩展子数组长度，直到不满足交替关系。
- 更新
ans为当前找到的子数组长度与之前记录的最大值之间的较大者。 - 重复上述过程，直到遍历完整个数组。
- 最后返回
ans。
代码实现
以下是基于上述思路的 Python 代码实现：
class Solution:def alternatingSubarray(self, nums: List[int]) -> int:ans = -1i, n = 0, len(nums)while i < n - 1:# 检查当前和下一个元素是否满足差为1if nums[i + 1] - nums[i] != 1:i += 1continue# 记录当前起始位置i0 = ii += 2# 检查后续元素是否满足交替关系while i < n and nums[i - 2] == nums[i]:i += 1# 更新答案ans = max(ans, i - i0)# 回退一位，以防漏掉可能的子数组i -= 1return ans
代码解析
-
初始化：
ans = -1：用于记录最长的交替子数组长度，初始设为-1表示尚未找到。i, n = 0, len(nums)：i为当前遍历的索引，n为数组长度。
-
主循环：
while i < n - 1：遍历数组，确保至少有两个元素可以比较。if nums[i + 1] - nums[i] != 1：检查当前元素与下一个元素的差是否为1，不满足则移动指针i。
-
找到可能的交替子数组起点：
i0 = i：记录子数组的起始位置。i += 2：跳过下一个元素，准备检查更长的子数组。
-
检查交替关系：
while i < n and nums[i - 2] == nums[i]：检查当前元素是否等于起始位置的元素，以维持交替关系。i += 1：如果满足条件，继续扩展子数组长度。
-
更新答案：
ans = max(ans, i - i0)：更新最长子数组长度。i -= 1：回退一位，防止遗漏潜在的子数组。
-
返回结果：
return ans：返回找到的最长交替子数组长度，如果没有则返回-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
输入：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
