线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多k个重复元素） 题目描述 给定一个整数数组 nums 和一个非负整数 k 。我们定义一个连续子序列是“有效的”，当且仅当在这个子序列中，任何一个值出现的次数都不超过 k 次。换句话说，子序列中最多允许同一个数字出现 k+1 次（即最多重复 k 次）。你的目标是找到并返回满足此条件的最长连续子序列的长度。 例如： 输入： nums = [1, 2, 1, 2, 1, 1, 1, 3], k = 1 输出： 5 解释：最长有效连续子序列是 [1, 2, 1, 2, 1] 或 [2, 1, 2, 1, 3] ，长度为5。其中任意数字（如1）出现的次数最多为2（即重复1次）。注意， [1, 1, 1, 1] 是无效的，因为1出现了4次，超过了 k+1=2 的限制。 解题过程 这个问题可以看作经典的“最长不含重复字符的子串”问题的推广。当 k=0 时，就是要求子序列中所有元素都不相同。当 k>0 时，允许有限的重复。 我们可以使用 滑动窗口 结合 哈希表 来高效解决。虽然滑动窗口通常不被严格归类为线性动态规划，但其核心思想（维护一个满足条件的最优区间）与线性DP中维护状态的思想是相通的。这里我们采用滑动窗口解法，因为它更直观高效。 核心思路 ： 我们维护一个滑动窗口 [left, right] ，表示当前考察的连续子序列。 用哈希表（比如字典） freq 来记录窗口内每个数字出现的频率。 不断向右移动窗口的右边界 right ，将 nums[right] 加入窗口，更新其频率。 在加入新元素后，检查窗口是否依然“有效”，即所有数字的频率是否都不超过 k 。如果某个数字的频率超过了 k ，说明当前窗口无效，需要收缩左边界 left ，直到窗口重新有效。 在窗口有效的每一个时刻，用当前窗口的长度 (right - left + 1) 更新全局最大长度。 详细步骤 ： 初始化 ： 设置两个指针 left = 0 和 right = 0 ，分别表示窗口的左右边界（初始窗口为空）。 使用一个字典（或哈希表） freq 来记录当前窗口内每个数字出现的次数。初始为空。 初始化结果变量 max_len = 0 。 遍历数组（扩张右边界） ： 我们遍历数组，每次循环中， right 从0到 n-1 （ n 是数组长度）。 将 nums[right] 加入窗口： freq[nums[right]] += 1 。 检查并维护窗口有效性（收缩左边界） ： 在加入新元素后，检查新元素 nums[right] 在窗口内的频率是否超过了 k 。注意，因为每次只加了一个元素，如果窗口无效，那一定是新加入的元素导致其频率超过了 k 。 如果 freq[nums[right]] > k ，说明当前窗口无效。我们需要收缩左边界 left ，直到 nums[right] 的频率降回到 k （即 freq[nums[right]] == k ）。 收缩左边界的方法是：将 nums[left] 从窗口中移除（即 freq[nums[left]] -= 1 ），然后将 left 向右移动一位。重复此过程直到 nums[right] 的频率不再超标。 更新答案 ： 在收缩完成后，当前窗口 [left, right] 一定是有效的。 计算窗口长度： current_len = right - left + 1 。 更新全局最大长度： max_len = max(max_len, current_len) 。 继续循环 ： 将 right 右移，重复步骤2-4，直到遍历完整个数组。 为什么这样做是正确的？ 我们保证了在任何时候，窗口 [left, right] 内部都是有效的（任何数字频率 ≤ k）。 当窗口因为加入新元素而变得无效时，我们只从左边移除元素，直到它重新有效。这不会错过更长的有效子序列，因为无效窗口是由于某个特定数字频率超标导致的，必须移除一些该数字的早期出现才能解决。 我们检查了所有以 right 结尾的有效窗口，并记录了其中最大的长度，因此最终得到的是全局最长有效子序列。 复杂度分析 ： 时间复杂度：O(n)。虽然内部有一个while循环来收缩左边界，但每个元素最多被加入和移出窗口各一次，因此总操作次数是 O(n)。 空间复杂度：O(n)，最坏情况下我们需要存储 n 个不同元素的频率（当 k=0 且数组元素都不同时，哈希表大小为 n ）。在数字范围有限的情况下，可以优化到 O(数字种类数)。 示例推演 （ nums = [1, 2, 1, 2, 1, 1, 1, 3], k = 1 ）： 初始化: left=0, max_ len=0, freq={} right=0: nums[ 0]=1, freq={1:1}，有效，max_ len=1 right=1: nums[ 1]=2, freq={1:1, 2:1}，max_ len=2 right=2: nums[ 2 ]=1, freq={1:2, 2:1}，1的频率=2>k=1，需要收缩。 移除nums[ left]=nums[ 0]=1, freq[ 1 ]=1, left=1。现在1的频率=1≤k，停止收缩。 窗口[ 1,2]有效，长度=2，max_ len保持2。 right=3: nums[ 3 ]=2, freq={1:1, 2:2}，2的频率=2>k，收缩。 移除nums[ left]=nums[ 1]=2, freq[ 2 ]=1, left=2。现在2的频率=1≤k。 窗口[ 2,3]有效，长度=2，max_ len保持2。 right=4: nums[ 4 ]=1, freq={1:2, 2:1}，1的频率=2>k，收缩。 移除nums[ left]=nums[ 2]=1, freq[ 1 ]=1, left=3。现在1的频率=1≤k。 窗口[ 3,4]有效，长度=2，max_ len保持2。 right=5: nums[ 5 ]=1, freq={1:2, 2:1}，1的频率=2>k，收缩。 移除nums[ left]=nums[ 3]=2, freq[ 2 ]=0, left=4。现在1的频率=2>k，继续收缩。 移除nums[ left]=nums[ 4]=1, freq[ 1 ]=1, left=5。现在1的频率=1≤k。 窗口[ 5,5]有效，长度=1，max_ len保持2。 right=6: nums[ 6 ]=1, freq={1:2}，1的频率=2>k，收缩。 移除nums[ left]=nums[ 5]=1, freq[ 1 ]=1, left=6。现在1的频率=1≤k。 窗口[ 6,6]有效，长度=1，max_ len保持2。 right=7: nums[ 7]=3, freq={1:1, 3:1}，有效，窗口[ 6,7]长度=2，max_ len保持2。 最终结果max_ len=5？等等，我们上面的推演似乎没有找到长度为5的窗口。因为我们是从左到右，每次保证以right结尾的窗口有效，但全局最长窗口可能出现在中间某个位置，不一定是某个right结尾的。我们重新审视算法：实际上，当right=7时，窗口应该是[ 6,7 ]吗？我们需要检查完整的遍历过程。 让我们从头用算法逻辑再走一遍，注意窗口收缩的规则是收缩到“新加入元素”的频率不超过k为止。在right=5时，我们得到窗口[ 5,5]（实际上我们可能错过了更优的窗口）。但仔细分析，在right=4时，窗口是[ 3,4]（元素[ 2,1]），当right=5加入1后，1的频率变成2，收缩左边界，直到移除一个1，使得1的频率降为1。在right=5这一步，收缩后left=5，窗口[ 5,5]（元素[ 1]）。这意味着我们丢弃了窗口[ 3,4]，因为它包含了两个1（在位置4和5）导致1的频率超标，但如果我们保留第一个1（位置2）而丢弃位置4的1呢？但窗口必须是连续的，我们无法跳过位置4的1。实际上，最长窗口[ 1,2,1,2,1]对应索引[ 0,4]，当我们right=4时，窗口应该是[ 0,4 ]？检查：在right=0,1,2,3,4时，每次加入后，1的频率是1,1,2,2,3？不对，我们需要更严谨地跟踪。 用代码逻辑模拟（每一步right）： right=0: 窗口[ 0,0]，freq{1:1}，有效，max_ len=1 right=1: 窗口[ 0,1]，freq{1:1,2:1}，有效，max_ len=2 right=2: 加入1，freq{1:2,2:1}，1的频率2>1，收缩：移除nums[ 0]=1，freq[ 1]=1，left=1。窗口[ 1,2]，有效，长度2，max_ len=2 right=3: 加入2，freq{1:1,2:2}，2的频率2>1，收缩：移除nums[ 1]=2，freq[ 2]=1，left=2。窗口[ 2,3]，有效，长度2，max_ len=2 right=4: 加入1，freq{1:2,2:1}，1的频率2>1，收缩：移除nums[ 2]=1，freq[ 1]=1，left=3。窗口[ 3,4]，有效，长度2，max_ len=2 right=5: 加入1，freq{1:2,2:1}，1的频率2>1，收缩：移除nums[ 3]=2，freq[ 2]=0，left=4；现在1的频率还是2>1，继续收缩：移除nums[ 4]=1，freq[ 1]=1，left=5。窗口[ 5,5]，有效，长度1，max_ len=2 right=6: 加入1，freq{1:2}，1的频率2>1，收缩：移除nums[ 5]=1，freq[ 1]=1，left=6。窗口[ 6,6]，有效，长度1，max_ len=2 right=7: 加入3，freq{1:1,3:1}，有效，窗口[ 6,7]长度2，max_ len=2 最终得到2，但实际答案是5。问题出在哪里？因为我们的收缩策略是移除左边元素直到新加入元素（nums[ right]）的频率不超过k。但在这个例子中，当right=5时，新加入元素1导致频率超标，我们收缩到left=5，但此时窗口[ 5,5]是有效的，但我们可能错过了更长的窗口，比如[ left, right]不是以right结尾的最长有效窗口吗？实际上，在right=5时，以索引5结尾的最长有效窗口是[ 3,5]（元素[ 2,1,1]）吗？检查[ 3,5]：元素2,1,1，其中1出现2次，刚好等于k+1=2，是允许的！因为k=1表示最多允许重复1次，即最多出现2次。所以[ 3,5]是有效的，但我们的算法为什么没有得到？因为我们的收缩条件是 freq[nums[right]] > k ，即当频率严格大于k时才收缩，而k=1时，频率允许为2。我们之前错误地认为频率不能超过k，实际上是允许重复k次，即频率最多为k+1。所以条件应该是 freq[nums[right]] > k+1 ？不对，题目定义是“任何值出现的次数都不超过k次”，即频率 ≤ k。那么k=1时，频率最多为1，不能为2。但题目例子中[ 1,2,1,2,1]中1出现了3次，超过了k=1？仔细看例子，k=1，最长子序列是[ 1,2,1,2,1]，其中1出现了3次，2出现了2次。这似乎与定义矛盾。实际上，我重新读题：“任何一个值出现的次数都不超过k次”，k=1，那么每个数字最多出现1次，但例子中1出现了3次。所以可能题目描述有歧义，正确的理解应该是“任何一个值最多允许重复k次”，即出现次数 ≤ k+1。通常这类问题称为“最多包含k个重复项的数组的最长子序列”。让我们修正理解：条件是每个数字在子序列中最多出现k+1次（即最多重复k次）。那么算法中，当 freq[nums[right]] > k+1 时才需要收缩。但例子中k=1，允许最多出现2次。在[ 1,2,1,2,1]中1出现了3次，超过2，所以应该是无效的。但例子说它是有效的？看来我误解了例子。让我们重新计算例子中的最长有效子序列：nums = [ 1,2,1,2,1,1,1,3], k=1。子序列[ 1,2,1,2,1]中1出现了3次，2出现了2次。如果允许最多出现k+1=2次，那么1出现3次超标，2出现2次刚好。所以这个子序列无效。但答案给的是5，对应的可能是[ 2,1,2,1,3]（1出现2次，2出现2次，3出现1次，都≤2，有效）。所以例子中第一个子序列其实是无效的，答案是第二个。我们算法的收缩条件应该是 freq[nums[right]] > k+1 。但k=1时，频率>2才收缩。在例子中，当right=4时，1的频率是3（在窗口[ 0,4 ]中），超过了2，所以会收缩。这样就能找到正确结果。 修正算法：条件为 freq[nums[right]] > k+1 时收缩。重新推演例子： right=0: 窗口[ 0,0]，freq{1:1}，有效，max_ len=1 right=1: 窗口[ 0,1]，freq{1:1,2:1}，有效，max_ len=2 right=2: 加入1，freq{1:2,2:1}，1的频率=2，不大于k+1=2，有效。窗口[ 0,2]长度3，max_ len=3 right=3: 加入2，freq{1:2,2:2}，2的频率=2，有效。窗口[ 0,3]长度4，max_ len=4 right=4: 加入1，freq{1:3,2:2}，1的频率=3>2，收缩：移除nums[ left]=nums[ 0]=1，freq[ 1]=2，left=1。窗口[ 1,4]长度4，max_ len保持4 right=5: 加入1，freq{1:3,2:2}，1的频率=3>2，收缩：移除nums[ left]=nums[ 1]=2，freq[ 2]=1，left=2；1的频率仍3>2，收缩：移除nums[ left]=nums[ 2]=1，freq[ 1]=2，left=3。窗口[ 3,5]长度3，max_ len保持4 right=6: 加入1，freq{1:3,2:1}，1的频率=3>2，收缩：移除nums[ left]=nums[ 3]=2，freq[ 2]=0，left=4；1的频率仍3>2，收缩：移除nums[ left]=nums[ 4]=1，freq[ 1]=2，left=5。窗口[ 5,6]长度2，max_ len保持4 right=7: 加入3，freq{1:2,3:1}，有效，窗口[ 5,7]长度3，max_ len保持4 得到4，但答案是5。我们漏掉了窗口[ 2,6]？检查[ 2,6]：索引2到6的元素是[ 1,2,1,1,1]，1出现了4次，超标。那窗口[ 1,5]：元素[ 2,1,2,1,1]，1出现3次，超标。窗口[ 0,4]我们已经考虑过了（长度5，但1出现3次超标，无效）。那答案5对应哪个窗口？可能是[ 1,5]？无效。再仔细看例子输出5，解释是[ 1,2,1,2,1]或[ 2,1,2,1,3 ]。第一个我们已判断无效（1出现3次），但题目中k=1，最多允许重复1次，即最多出现2次。所以例子中的答案似乎是矛盾的。查阅类似题目（LeetCode 395. Longest Substring with At Least K Repeating Characters）是要求每个字符出现次数至少k次，但这里是“不超过k次”。另一种常见题目是“最多包含k个不同元素的最长子数组”，但这里是“每个元素最多重复k次”。实际上，我回忆LeetCode 340. Longest Substring with At Most K Distinct Characters 是最多k个不同字符，而本题是每个字符最多重复k次，即每个字符出现次数≤k。那么k=1时，每个字符最多出现1次，就是无重复字符的最长子串。但例子中显然有重复。所以我对题目的理解可能有误。 鉴于这种不确定性，我重新定义题目：给定整数数组nums和整数k，找到最长连续子数组，其中每个数字出现的次数 最多为k （即≤k）。那么k=1时，每个数字最多出现1次，即无重复。但例子中答案5显然不符合。可能题目意图是“最多允许k个重复”，即每个数字最多出现k+1次。我们按照“最多允许k个重复”来继续，即条件为 freq[ num] ≤ k+1。但例子答案5与k=1时 freq≤2 相符，窗口[ 2,1,2,1,3]中1出现2次，2出现2次，3出现1次，都≤2，有效。窗口[ 1,2,1,2,1]中1出现3次无效。所以例子答案5是有效的。我们算法得到4，是因为我们收缩时，当freq[ nums[ right]] > k+1 才收缩。在right=4时，1的频率变成3>2，我们收缩到left=1，窗口[ 1,4]长度4。但实际上，存在以right=4结尾的更长的有效窗口吗？比如窗口[ 0,4]无效（1的频率3）。窗口[ 1,4]有效，长度4。窗口[ 2,4]长度3。所以以right=4结尾的最长有效窗口就是[ 1,4]长度4。同理，以right=5结尾的有效窗口最长是[ 3,5]长度3。以right=6结尾的有效窗口最长是[ 5,6]长度2。以right=7结尾的有效窗口最长是[ 5,7]长度3。所以全局最长是4，但答案是5，说明有窗口长度5，比如[ 0,4]无效，[ 1,5]无效，[ 2,6]无效，[ 3,7]：元素[ 2,1,1,1,3]中1出现3次无效，[ 0,5]更长但无效。所以答案5对应的窗口是什么？可能是[ 0,4]？但我们已判无效。让我们直接计算例子数组：nums = [ 1,2,1,2,1,1,1,3 ]，k=1。我们人工找最长子数组，其中每个数字最多出现2次： 从索引0开始，[ 1,2,1,2,1 ] 中1出现3次，无效。 子数组[ 2,1,2,1,3] 从索引1到5？索引1~5是[ 2,1,2,1,1]，1出现3次无效。索引2~6是[ 1,2,1,1,1]无效。索引3~7是[ 2,1,1,1,3]无效。索引0~4无效，1~5无效，2~6无效，3~7无效。那长度5的有效子数组在哪？可能是我漏掉了索引0~4是[ 1,2,1,2,1]无效。索引1~5无效。索引2~6无效。索引3~7无效。所以不存在长度5的有效子数组？但题目说答案是5，可能是[ 1,2,1,2,3 ]？但3在索引7，要包含3必须到索引7，但中间有额外的1。所以可能题目描述和例子不一致。为了不陷入例子，我们明确算法解决的一般性问题： 问题重述 ：给定数组nums和整数k，找到最长连续子数组，使得其中任意数字的出现次数不超过k（即≤k）。这才是常见表述。当k=1时，就是无重复字符的最长子串。但例子中k=1，答案5，说明例子不是这个意思。所以例子可能是另一种理解：每个数字最多重复k次，即出现次数≤k+1。但例子中k=1，出现次数≤2，那么[ 1,2,1,2,1]中1出现3次无效。所以例子可能给错了，或者是另一种变体：允许最多k个重复，但重复指的是连续重复？比如“最多允许连续k个相同数字”。但题目说“线性动态规划：统计只出现一次的最长连续子序列的长度（变种：允许最多k个重复元素）”，从标题看，是“统计只出现一次的最长连续子序列”，变种允许最多k个重复元素。所以可能是“最长连续子序列，其中每个数字最多连续出现k次”？但例子中1连续出现了多次（位置4,5,6连续三个1），如果k=1，则不允许连续两个相同的，所以最长应该是4，比如[ 1,2,1,2]或[ 2,1,2,1 ]等。但例子答案是5，所以也不是连续重复。 鉴于这种混乱，我们聚焦于算法本身。算法可以解决两种常见变体： 每个数字出现次数 ≤ k（严格不超过k次）。 每个数字出现次数 ≤ k+1（即最多允许重复k次）。 我们只需在收缩条件上调整。通常的“最多包含k个重复项的最长子数组”是允许重复k次，即出现次数≤k。但k=1时，最多出现1次，就是无重复。但例子中k=1，答案5，意味着允许出现2次，即≤2。所以可能是允许重复1次，即出现次数≤2。所以条件为 ≤ k+1。 我们采用更一般的描述：给定整数k，子数组中任何数字的出现次数不能超过一个限制limit。当limit = 1时，就是无重复；当limit = k+1时，就是允许重复k次。题目中“允许最多k个重复元素”可能意味着limit = k+1。我们按此实现。 修正算法：收缩条件为 freq[nums[right]] > limit ，其中 limit = k+1。 重新推演例子，limit=2： right=0: 窗口[ 0,0]，freq{1:1}，有效，max_ len=1 right=1: 窗口[ 0,1]，freq{1:1,2:1}，有效，max_ len=2 right=2: 加入1，freq{1:2,2:1}，1的频率=2，不大于limit=2，有效。窗口[ 0,2]长度3，max_ len=3 right=3: 加入2，freq{1:2,2:2}，有效，窗口[ 0,3]长度4，max_ len=4 right=4: 加入1，freq{1:3,2:2}，1的频率=3>2，收缩：移除nums[ 0]=1，freq[ 1]=2，left=1。窗口[ 1,4]长度4，max_ len保持4 right=5: 加入1，freq{1:3,2:2}，1的频率=3>2，收缩：移除nums[ 1]=2，freq[ 2]=1，left=2；1的频率仍3>2，收缩：移除nums[ 2]=1，freq[ 1]=2，left=3。窗口[ 3,5]长度3，max_ len保持4 right=6: 加入1，freq{1:3,2:1}，1的频率=3>2，收缩：移除nums[ 3]=2，freq[ 2]=0，left=4；1的频率仍3>2，收缩：移除nums[ 4]=1，freq[ 1]=2，left=5。窗口[ 5,6]长度2，max_ len保持4 right=7: 加入3，freq{1:2,3:1}，有效，窗口[ 5,7]长度3，max_ len保持4 还是得到4。但实际存在长度5的窗口吗？我们检查以right=7结尾的窗口，从left=5开始，元素[ 1,1,3]中1出现2次，有效，但长度3。从left=4开始，元素[ 1,1,1,3]中1出现3次无效。从left=3开始，元素[ 2,1,1,1,3]中1出现3次无效。所以没有长度5的有效窗口。那答案5从何而来？也许窗口可以不连续？但题目说是连续子序列。可能我漏掉了窗口[ 2,6]？[ 1,2,1,1,1]中1出现4次无效。所以答案5是错的？我怀疑例子的k=1应该是允许每个数字最多出现2次，但数组是[ 1,2,1,2,1,1,1,3]，最长有效子数组是[ 1,2,1,2,1]？但1出现3次>2。除非k=2，允许最多出现3次。如果k=2，limit=3，那么[ 1,2,1,2,1 ]中1出现3次，有效。此时答案可能是5。但题目给的是k=1。可能是笔误。 为了避免例子误导，我们忽略例子，直接给出通用解法。算法可以适用于任意limit（即最多允许出现limit次）。对于“允许最多k个重复元素”，通常limit = k+1。 最终算法步骤 （设限制为limit，即子数组中任何数字出现次数 ≤ limit）： 初始化 left = 0, max_ len = 0，哈希表 freq 记录窗口内数字频率。 遍历 right 从 0 到 n-1： a. 将 nums[ right] 加入 freq，freq[ nums[ right] ]++。 b. 如果 freq[ nums[ right]] > limit，说明 nums[ right ] 的频率超标，不断收缩左边界： freq[ nums[ left]]--，left++，直到 freq[ nums[ right] ] == limit。 （注意：循环条件是 while freq[ nums[ right]] > limit，因为可能收缩过程中移除了其他数字，但 nums[ right ] 的频率可能还没降到 limit，所以需要继续收缩） c. 此时窗口 [ left, right] 有效，更新 max_ len = max(max_ len, right-left+1)。 返回 max_ len。 时间复杂度 O(n)，空间复杂度 O(不同数字的数量)。 举例 ：设 limit=2（即允许最多重复1次），nums=[ 1,2,1,2,1,1,1,3 ]，算法得到4，但可能题目期望的是5，所以我们不纠结例子。如果题目意图是每个数字最多出现k次（即 ≤ k），则 limit=k。对于 k=1，就是无重复字符的最长子串。 你可以根据具体题目要求调整 limit 的值。这个滑动窗口算法是线性时间复杂度，且易于实现。