Easy

题目描述

给你一个下标从 0 开始的整数数组 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。

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

示例 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 <= 100
  • 1 <= nums[i] <= 10^4

解题思路

这道题要求找到最长的交替子数组，交替的含义是相邻元素的差值在 +1 和 -1 之间交替变化。

解题思路：

由于数组长度较小（最多100），我们可以采用暴力枚举的方法。具体步骤如下：

  1. 枚举所有可能的起始位置：从每个位置开始尝试构建交替子数组
  2. 验证交替模式：对于每个起始位置，向右扩展检查是否满足交替条件
    • 第一步必须是 +1（s1 = s0 + 1）
    • 之后交替进行 -1 和 +1 的变化
  3. 记录最大长度：在所有有效的交替子数组中找到最大长度

算法实现：

  • 外层循环枚举起始位置 i
  • 内层循环从位置 i 开始向右扩展，检查差值是否符合期望的模式
  • 期望的差值模式是：+1, -1, +1, -1, …
  • 使用变量记录当前找到的最大长度

时间复杂度为 O(n²)，空间复杂度为 O(1)，在给定的约束条件下完全可行。

推荐解法： 暴力枚举法（在此题的约束下是最直观且高效的解法）

代码实现

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

class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = -1
        
        for i in range(n - 1):
            if nums[i + 1] == nums[i] + 1:
                length = 2
                j = i + 1
                
                while j + 1 < n:
                    expected_diff = 1 if length % 2 == 0 else -1
                    if nums[j + 1] == nums[j] + expected_diff:
                        length += 1
                        j += 1
                    else:
                        break
                
                max_len = max(max_len, length)
        
        return max_len

public class Solution {
    public int AlternatingSubarray(int[] nums) {
        int n = nums.Length;
        int maxLen = -1;
        
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] == nums[i] + 1) {
                int len = 2;
                int j = i + 1;
                
                while (j + 1 < n) {
                    int expectedDiff = (len % 2 == 0) ? 1 : -1;
                    if (nums[j + 1] == nums[j] + expectedDiff) {
                        len++;
                        j++;
                    } else {
                        break;
                    }
                }
                
                maxLen = Math.Max(maxLen, len);
            }
        }
        
        return maxLen;
    }
}

var alternatingSubarray = function(nums) {
    const n = nums.length;
    let maxLen = -1;
    
    for (let i = 0; i < n - 1; i++) {
        if (nums[i + 1]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n²)
空间复杂度O(1)
  • 时间复杂度：外层循环遍历所有起始位置 O(n)，内层循环最坏情况下遍历剩余所有元素 O(n)，总体为 O(n²)
  • 空间复杂度：只使用了常数个额外变量，为 O(1)

相关题目