线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多K个重复元素）

题目描述
给定一个整数数组 nums 和一个非负整数 k，你需要找到最长的连续子数组的长度，使得这个子数组中每个数字最多出现 k 次。换句话说，子数组中任意数字的出现次数都不能超过 k。

示例
输入：nums = [1, 2, 3, 1, 2, 3, 1, 2], k = 2
输出：6
解释：最长的合法子数组是 [2, 3, 1, 2, 3, 1] 或 [3, 1, 2, 3, 1, 2]，长度是 6，其中每个数字最多出现 2 次。

解题过程循序渐进讲解

步骤 1：理解问题
我们要找的是一个连续子数组（即原数组的一段连续部分），这个子数组要满足条件：子数组里任何一个数字出现的次数 ≤ k。
这是一个典型的滑动窗口问题，但也可以用动态规划的思路来思考。由于涉及“连续”和“出现次数限制”，滑动窗口是更自然的选择，但我们可以用动态规划来辅助理解状态转移。

为什么可以看作线性动态规划？
定义 dp[r] 为以位置 r 结尾的、满足条件的最长子数组的起始位置（或长度）。
我们需要在遍历右端点 r 时，通过维护一个合法窗口，不断更新左端点 l，使得窗口 [l, r] 内所有数字出现次数 ≤ k。
最终答案就是所有窗口中最大的长度 (r - l + 1)。
这是一种“双指针 + 计数”的动态规划思路，状态转移是线性的。

步骤 2：暴力法思路
枚举所有子数组 [i, j]，检查每个子数组是否满足条件（每个数字出现次数 ≤ k）。
时间复杂度 O(n²)，不可取。

步骤 3：滑动窗口优化
我们用一个哈希表（字典） count 记录当前窗口 [l, r] 内每个数字出现的次数。
遍历右端点 r，每次将 nums[r] 加入窗口，更新 count[nums[r]]。
如果加入后 nums[r] 的出现次数超过 k，说明窗口不合法，需要将左端点 l 右移，直到 nums[r] 的次数 ≤ k。
在移动左端点时，要减少移出数字的计数。

举例
nums = [1, 2, 3, 1, 2, 3, 1, 2], k = 2
初始 l = 0, r 从 0 到 7：

• r=0, 窗口[1], count[1]=1 ≤2, 长度=1
• r=1, 窗口[1,2], 都 ≤2, 长度=2
• r=2, 窗口[1,2,3], 长度=3
• r=3, 加入1后 count[1]=2，仍合法，长度=4
• r=4, 加入2后 count[2]=2，仍合法，长度=5
• r=5, 加入3后 count[3]=2，仍合法，长度=6
• r=6, 加入1后 count[1]=3 > k=2 → 不合法，需移动 l 直到 count[1] ≤2。
  移动 l 从 0 到 1，移出 nums[0]=1，count[1] 变为 2，合法。新窗口 [2,3,1,2,3,1] 长度=6。
• r=7, 加入2后 count[2]=3 > k=2 → 不合法，移动 l 直到 count[2] ≤2。
  移动 l 从 1 到 2，移出 nums[1]=2，count[2] 变为 2，合法。窗口变为 [3,1,2,3,1,2] 长度=6。

最终最大长度是 6。

步骤 4：动态规划状态设计
我们可以定义状态 dp[r] 表示以 r 结尾的最长子数组的起始位置 l。
转移方程：

• 当加入 nums[r] 后，如果 nums[r] 在窗口中出现次数超过 k，就向右移动 l，直到次数 ≤ k。
• 更新 dp[r] = l。
  那么以 r 结尾的合法子数组长度是 r - dp[r] + 1。
  最终答案是所有长度的最大值。

伪代码

初始化哈希表 count
l = 0
max_len = 0
for r in 0..n-1:
    count[nums[r]] += 1
    while count[nums[r]] > k:
        count[nums[l]] -= 1
        l += 1
    max_len = max(max_len, r - l + 1)
返回 max_len

步骤 5：复杂度分析

• 时间复杂度 O(n)：每个元素最多被加入窗口一次、移出窗口一次。
• 空间复杂度 O(n)：哈希表存储不同数字的出现次数。

步骤 6：边界与特殊情况

• 如果 k=0，那么任何数字不能重复，相当于找最长无重复字符的子串。
• 如果 k ≥ 数组最大频次，那么整个数组都合法。

步骤 7：代码示例（Python）

def longest_subarray_with_at_most_k_duplicates(nums, k):
    from collections import defaultdict
    count = defaultdict(int)
    l = 0
    max_len = 0
    for r in range(len(nums)):
        count[nums[r]] += 1
        while count[nums[r]] > k:
            count[nums[l]] -= 1
            l += 1
        max_len = max(max_len, r - l + 1)
    return max_len

总结
这道题是“最多包含 k 个重复数字的最长连续子数组”问题，通过滑动窗口（双指针）在线性时间内解决。虽然它更偏向双指针，但状态转移可视为线性动态规划的一种变形，适用于处理“连续子数组 + 频次限制”的场景。