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

题目链接

长度最长的最多有k个频率的子数组

题目描述

给定一个整数数组 nums 和一个整数 k，找出最长子数组的长度，使得子数组中每个元素的出现次数最多为 k 次。

解法分析：滑动窗口法

核心思路

该解法采用滑动窗口技术，通过维护一个窗口，确保窗口内每个元素的出现次数不超过k次。当某个元素的出现次数超过k时，移动左指针收缩窗口，直到满足条件。最终窗口的最大长度即为所求。

代码实现

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        m = {}  # 记录窗口内元素的频率
        l = ans = 0  # 左指针、最大子数组长度
        for r in range(len(nums)):
            # 更新当前元素的频率
            m[nums[r]] = m.get(nums[r], 0) + 1
            
            # 当当前元素频率超过k时，收缩左边界
            while m[nums[r]] > k:
                m[nums[l]] -= 1  # 减少左指针处元素的频率
                l += 1  # 左指针右移
            
            # 更新最大子数组长度
            ans = max(ans, r - l + 1)
        
        return ans

代码解析

1. 初始化变量：

   • m：字典，用于记录窗口内每个元素的出现频率
   • l：滑动窗口的左指针，初始位置为0
   • ans：记录最长子数组的长度，初始为0

2. 遍历数组：

   • 右指针r从0开始遍历数组，扩展窗口
   • m[nums[r]] = m.get(nums[r], 0) + 1：更新当前元素在窗口中的频率，使用dict.get方法避免键不存在的问题

3. 调整窗口：

   • 当m[nums[r]] > k时，说明当前元素的出现次数超过k次
   • m[nums[l]] -= 1：减少左指针处元素的频率
   • l += 1：左指针右移，收缩窗口，直到当前元素的频率≤k

4. 更新最长长度：

   • ans = max(ans, r - l + 1)：计算当前窗口的长度并更新最长长度
   • 窗口长度为r - l + 1，表示从左指针到右指针的子数组长度

关键逻辑说明

• 频率记录：使用字典m记录每个元素在窗口中的出现频率，确保可以快速查询和更新
• 窗口调整：当某个元素的频率超过k时，左指针向右移动，直到该元素的频率≤k，保证窗口内所有元素的频率都不超过k
• 动态更新：每次调整窗口后，计算当前窗口长度并更新最大值

复杂度分析

• 时间复杂度：O(n)，其中n是数组的长度。每个元素最多被左右指针各访问一次，总操作次数不超过2n。
• 空间复杂度：O(m)，其中m是窗口中不同元素的数量，最坏情况下为O(n)。

示例详解

以输入nums = [1,2,2,3,3,3,4,4,4,4], k = 2为例：

1. 初始化：m={}, l=0, ans=0

2. r=0，元素1：

   • m[1] = 0 + 1 = 1
   • m[1] = 1 ≤ 2，不收缩窗口
   • 窗口长度：0-0+1=1，ans=1

3. r=1，元素2：

   • m[2] = 0 + 1 = 1
   • m[2] = 1 ≤ 2，不收缩窗口
   • 窗口长度：1-0+1=2，ans=2

4. r=2，元素2：

   • m[2] = 1 + 1 = 2
   • m[2] = 2 ≤ 2，不收缩窗口
   • 窗口长度：2-0+1=3，ans=3

5. r=3，元素3：

   • m[3] = 0 + 1 = 1
   • m[3] = 1 ≤ 2，不收缩窗口
   • 窗口长度：3-0+1=4，ans=4

6. r=4，元素3：

   • m[3] = 1 + 1 = 2
   • m[3] = 2 ≤ 2，不收缩窗口
   • 窗口长度：4-0+1=5，ans=5

7. r=5，元素3：

   • m[3] = 2 + 1 = 3
   • m[3] = 3 > 2，进入收缩：
     • m[1] = 1 - 1 = 0，l=1
     • m[2] = 2 - 1 = 1，l=2
     • m[2] = 1 - 1 = 0，l=3
     • m[3] = 3 - 1 = 2，l=4
   • 窗口长度：5-4+1=2，ans=5

8. r=6，元素4：

   • m[4] = 0 + 1 = 1
   • m[4] = 1 ≤ 2，不收缩窗口
   • 窗口长度：6-4+1=3，ans=5

9. r=7，元素4：

   • m[4] = 1 + 1 = 2
   • m[4] = 2 ≤ 2，不收缩窗口
   • 窗口长度：7-4+1=4，ans=5

10. r=8，元素4：

    • m[4] = 2 + 1 = 3
    • m[4] = 3 > 2，进入收缩：
      • m[3] = 2 - 1 = 1，l=5
      • m[3] = 1 - 1 = 0，l=6
      • m[4] = 3 - 1 = 2，l=7
    • 窗口长度：8-7+1=2，ans=5

11. r=9，元素4：

    • m[4] = 2 + 1 = 3
    • m[4] = 3 > 2，进入收缩：
      • m[4] = 3 - 1 = 2，l=8
    • 窗口长度：9-8+1=2，ans=5

12. 最终返回5，即最长子数组长度为5。

总结

该解法利用滑动窗口技术高效地解决了寻找最多k个频率的最长子数组问题。核心在于维护一个窗口，确保窗口内每个元素的出现次数不超过k次，当超过时收缩左边界。这种方法避免了暴力枚举所有子数组的O(n²)复杂度，将时间复杂度优化到O(n)。

滑动窗口的关键步骤：

1. 使用字典记录元素频率
2. 右指针扩展窗口，左指针按需收缩
3. 实时更新最长子数组长度

这种思路适用于解决各种"元素频率约束"的子数组问题，是滑动窗口技术的经典应用场景。