2958. 最多 K 次重复元素的最长子数组

🎯 问题描述（来源于LeetCode）

描述：
给你一个整数数组 nums 和一个整数 k。
如果一个子数组中每个元素的出现次数都不超过 k 次，我们就称这个子数组是好子数组。
请你返回 nums 中最长好子数组的长度。

说明：

  • 这是一个不定长滑动窗口问题。

  • 核心逻辑是维护一个窗口，使得窗口内任意元素的出现次数都不超过 k 次。

  • 当某个元素的出现次数超过 k 时，收缩左边界。

  • 示例：

  • 示例 1：

1
2
3
4
5
输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：
子数组 [1,2,3,1,2,3] (索引 0 到 5) 中，1, 2, 3 各出现 2 次，满足条件。
如果再加一个 1，1 的出现次数变为 3，超过 k=2。
  • 示例 2：
1
2
3
4
输入：nums = [1,2,1,2,1,2,1,2], k = 1
输出：2
解释：
每个元素最多出现 1 次。最长好子数组是 [1,2] 或 [2,1]。

💻 解题思路

思路1：不定长滑动窗口

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        count = Counter()   # 哈希表，记录窗口内每个数字出现的次数
        result = 0          # 记录最长好子数组的长度
        left = 0            # 窗口左边界
        
        # 右边界 right 随循环遍历数组
        for right, num in enumerate(nums):
            # 1. 扩展窗口：将当前数字加入哈希表
            count[num] += 1
            
            # 2. 收缩窗口：如果当前数字出现次数超过 k
            # 则不断移动左边界，直到当前数字次数恢复为 k 或更少
            while count[num] > k:
                count[nums[left]] -= 1
                left += 1
            
            # 3. 更新结果：此时窗口 [left, right] 内所有数字出现次数 <= k
            result = max(result, right - left + 1)
            
        return result

思路1：📊 性能分析

  • 时间复杂度：O(N)O(N)
    • 其中 NN 是数组 nums 的长度。
    • 虽然代码中有一个 while 循环嵌套在 for 循环中，但每个元素最多被访问两次（一次被右边界 right 加入，一次被左边界 left 移出）。因此，整体操作次数是线性的。
  • 空间复杂度：O(N)O(N)
    • 哈希表 count 在最坏情况下（数组所有元素都不同）需要存储 NN 个键值对。

思考

  1. 通用模板：

    • 这道题是“无重复字符的最长子串”（k=1）和“水果成篮”（每个篮子无限容量，但种类限制为2，略有不同）的变体。
    • 更准确地说，它是“每个字符最多出现 k 次”的通用版本。
    • 代码逻辑非常简洁，只需将判断条件设为 count[num] > k 即可。

  2. 收缩逻辑：

    • while count[num] > k: 保证了窗口的合法性。
    • 当某个数字 num 的出现次数超过 k 时，我们不断移除左边的元素，直到 num 的次数降回 k。

  3. 不需要删除键：

    • 与之前的题目一样，这里也不需要 del count[nums[left]]。
    • 因为 Counter 允许值为 0 的键存在，且判断条件只关心是否大于 k。

  4. 结果更新：

    • result = max(result, right - left + 1) 放在 while 循环之后。
    • 确保只有在窗口合法（所有元素出现次数 <= k）时，才更新最大长度。