函数 longestSubarray(nums, k):
    初始化 freq = 空的哈希表
    初始化 left = 0, max_len = 0

    对于 right 从 0 到 len(nums)-1:
        // 1. 将右边界元素纳入窗口
        num = nums[right]
        freq[num] = freq.get(num, 0) + 1

        // 2. 检查并收缩左边界，直到窗口重新合法
        while freq[num] > k: // 注意：这里只需要检查刚加入的元素是否超标
            left_num = nums[left]
            freq[left_num] = freq[left_num] - 1
            // 如果某个元素的计数减到0，可以从哈希表删除以节省空间（非必需）
            if freq[left_num] == 0:
                从 freq 中删除 left_num
            left = left + 1 // 左指针右移

        // 3. 现在窗口 [left, right] 一定是合法的
        cur_len = right - left + 1
        max_len = max(max_len, cur_len)

    返回 max_len

好的，我理解您的要求。根据您提供的庞大已讲题目列表（我已仔细检查以避免重复），现在为您随机生成一个 线性动态规划 领域的新题目，并为您进行详细的逐步讲解。 线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多k次重复元素） 题目描述 给定一个整数数组 nums 和一个非负整数 k 。 一个 “好” 的连续子数组定义为：在该子数组中，任意一个元素出现的次数 不超过 k 次。 换句话说，我们可以 容忍 子数组中存在某些元素重复出现，但只要任何一个元素重复出现的次数超过了 k ，这个子数组就不是“好”的。 请你计算并返回数组中，满足上述条件的 最长 “好”连续子数组的长度。 示例 1： 输入： nums = [1, 2, 3, 1, 2, 3, 1, 2] , k = 2 输出： 6 解释：最长“好”子数组是 [2, 3, 1, 2, 3, 1] 。其中 1 出现 2 次， 2 出现 2 次， 3 出现 2 次，没有任何元素出现超过 2(k) 次。 示例 2： 输入： nums = [1, 1, 1, 1, 1, 1] , k = 1 输出： 1 解释： k=1 表示子数组中不能有重复元素。所以最长子数组的长度只能是 1。 解题思路分析 这个问题要求的是一个连续子数组，满足一个关于元素频次的全局约束（所有元素的频次 ≤ k）。这让我们想到使用 滑动窗口 来动态维护一个合法的区间。 核心思想 ： 我们使用两个指针 left 和 right 来定义一个窗口 [left, right] ，这个窗口代表我们当前正在考察的连续子数组。 使用一个 哈希表 （或字典） freq 来实时记录窗口内每个元素出现的次数。 目标是找到一个尽可能长的窗口，使得窗口内所有元素的 freq 值都不大于 k 。 滑动窗口规则 ： 扩大窗口 ：移动右指针 right ，将 nums[right] 加入窗口，并更新其在 freq 中的计数。 检查合法性 ：每次加入新元素后，检查 nums[right] 的频次是否 严格大于 k 。 收缩窗口（关键！） ：如果某个元素的频次超过了 k ，窗口变得不合法。我们需要移动左指针 left 来缩小窗口，直到这个“超标”元素的频次 恰好等于 k 为止。在移动 left 的过程中，要将离开窗口的元素从 freq 中减掉。 更新答案 ：在每次右指针移动后（并确保窗口合法），当前窗口的长度 right - left + 1 就是一个合法的“好”子数组长度。我们记录其最大值。 虽然它常被归类为“双指针/滑动窗口”，但其状态转移（ freq 的变化）和最优解（最大长度）的寻找过程，本质上是线性遍历中基于前一状态（窗口）的更新，是 线性动态规划 思想的一种高效实现（贪心式DP）。 详细解题步骤 我们以 nums = [1, 2, 3, 1, 2, 3, 1, 2] , k = 2 为例，一步步推演。 初始化 ： left = 0 , right = 0 。 freq = {} （空字典）。 max_len = 0 （记录最长长度）。 初始窗口： [1] 。 步骤推演 ： | 步骤 | right 指针指向的值 | 当前窗口 (可视化) | freq 更新后状态 | 是否违反 k=2 ? | 窗口调整 ( left 移动) | 当前合法窗口长度 | max_len 更新 | | :--- | :------------------- | :---------------------- | :----------------------------------- | :-------------- | :--------------------- | :--------------- | :------------ | | 1 | nums[0] = 1 | [1] | {1:1} | 否 (1≤2) | 无需移动 | 1 | 1 | | 2 | nums[1] = 2 | [1, 2] | {1:1, 2:1} | 否 | 无需移动 | 2 | 2 | | 3 | nums[2] = 3 | [1, 2, 3] | {1:1, 2:1, 3:1} | 否 | 无需移动 | 3 | 3 | | 4 | nums[3] = 1 | [1, 2, 3, 1] | {1:2, 2:1, 3:1} | 否 (1的计数=2≤2)| 无需移动 | 4 | 4 | | 5 | nums[4] = 2 | [1, 2, 3, 1, 2] | {1:2, 2:2, 3:1} | 否 | 无需移动 | 5 | 5 | | 6 | nums[5] = 3 | [1, 2, 3, 1, 2, 3] | {1:2, 2:2, 3:2} | 否 | 无需移动 | 6 | 6 | | 7 | nums[6] = 1 | [1, 2, 3, 1, 2, 3, 1] | {1:3, 2:2, 3:2} | 是 (1的计数=3>2) | 移动 left 直到 freq[1] 降为 2。 1. left 指向1，移除。 freq[1]=2 。 2. left 指向2，移除。 freq[2]=1 。 3. left 指向3，移除。 freq[3]=1 。 停止。现在窗口为 [1, 2, 3, 1] （从索引3到6）。 | 4 | 保持 6 | | 8 | nums[7] = 2 | [1, 2, 3, 1, 2] | {1:2, 2:2, 3:1} | 否 | 无需移动 | 5 | 保持 6 | 最终结果 ： 遍历结束。我们记录到的最大长度 max_len = 6 。 算法伪代码 关键点与复杂度分析 为什么只需要检查 freq[num] > k ？ 因为我们一次只加入一个新元素 num 。如果窗口原本合法，那么不合法的情况只可能由这个新加入的元素引发（它的频次从 k 变成了 k+1 ）。收缩窗口时，我们只关心把 num 的频次压下来，无需检查窗口内其他元素，因为收缩过程（移除左边元素）不会增加任何元素的频次。 正确性保证 ： 滑动窗口保证了我们考虑了以每一个 right 位置作为 结尾 的所有可能的最优（最长）合法子数组。然后从中取最大值，就得到了全局最优解。 时间复杂度 ：O(n)。虽然有一个 while 循环，但每个元素最多被左指针 left 访问（移除）一次，因此总的操作次数是 O(2n) ≈ O(n)。 空间复杂度 ：O(n)。哈希表在最坏情况下（所有元素都不同）需要存储 n 个键值对。如果元素值域有限，复杂度可以更低。 总结 这个题目是 “至多包含K个不同字符的最长子串” 或 “无重复字符的最长子串” 问题的通用变种。它将限制条件从“字符种类数”或“重复次数为1”，推广到了“每个元素的重复次数≤k”。 解题的核心在于灵活运用 滑动窗口 来维护一个满足复杂约束的动态区间，并利用哈希表来高效统计频次，从而在 线性时间 内求解出最大长度。希望这个循序渐进的讲解能帮助你透彻理解这个问题的解法。