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

标签: 数组 哈希表 滑动窗口

难度: Medium

给你一个整数数组 nums 和一个整数 k 。

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。

请你返回 nums 中 最长好 子数组的长度。

子数组 指的是一个数组中一段连续非空的元素序列。

示例 1：

输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
最长好子数组的长度为 6 。

示例 2：

输入：nums = [1,2,1,2,1,2,1,2], k = 1
输出：2
解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
最长好子数组的长度为 2 。

示例 3：

输入：nums = [5,5,5,5,5,5,5], k = 4
输出：4
解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
最长好子数组的长度为 4 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= nums.length

Submission

运行时间: 224 ms

内存: 31.4 MB

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)

        cnt = defaultdict(int)

        ans = l = 0
        for r in range(n):

            cnt[nums[r]] += 1
            if cnt[nums[r]] > k:
                ans = max(ans, r-l)
                while nums[l] != nums[r]:
                    cnt[nums[l]]-=1
                    l+=1
                cnt[nums[l]] -= 1
                l+=1

        ans = max(ans, r-l+1)
        return ans

Explain

此题解采用了滑动窗口的方法来找出最长的好子数组。通过一个左指针l和一个右指针r来定义窗口的边界。随着右指针r的向右移动，使用哈希表cnt来记录窗口内每个元素的出现次数。每次右指针向右移动时，将新的元素加入计数，如果此元素的计数超过k，则记录当前窗口的长度，并调整左指针l，直到该元素的计数不超过k。这样可以确保窗口内的所有元素频率都不超过k，从而找到满足条件的最长子数组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        n = len(nums)  # 数组的长度

        cnt = defaultdict(int)  # 存储元素及其频率的哈希表

        ans = l = 0  # 初始化最长长度ans和左指针l
        for r in range(n):  # 主循环，r为右指针

            cnt[nums[r]] += 1  # 将右指针指向的元素加入计数
            if cnt[nums[r]] > k:  # 如果计数超过k
                ans = max(ans, r-l)  # 更新最长好子数组的长度
                while nums[l] != nums[r]:  # 调整左指针，直到当前元素的计数不超过k
                    cnt[nums[l]] -= 1
                    l += 1
                cnt[nums[l]] -= 1  # 对于左指针指向的当前元素也要减少计数
                l += 1  # 移动左指针

        ans = max(ans, r-l+1)  # 处理最后一个窗口的长度
        return ans

Explore

在算法中，每次当右指针`r`向右移动并发现一个元素的计数超过了`k`时，就会更新`ans`记录当前的最长好子数组长度。这是在前一个元素的计数导致窗口不再有效时进行的。随后，左指针`l`被调整直到窗口内的所有元素的频率都不超过`k`。因此，每次窗口状态变化都会考虑是否更新`ans`，确保覆盖了所有可能的最长好子数组的情况。

当元素频率超过`k`时，说明当前窗口已经不满足题目条件（即窗口内的所有元素的频率都不超过`k`）。为了快速恢复窗口的有效性，最直接的方法是减少窗口内频率超标的元素数量，这可以通过移动左指针`l`实现。这种方法可以直接减少特定元素的计数，而如果采用其他方法如重新构建窗口或跳过某些元素，则可能导致较大的时间开销和复杂性增加。

在循环结束后需要再次更新`ans`是因为循环内部更新`ans`的条件是元素的计数超过`k`时，这时会提前结束当前窗口的考察。如果整个数组被遍历完而没有触发计数超过`k`的情况，最后一个窗口可能不会在循环中被正确地更新。因此，循环结束后需要再次检查并更新`ans`以确保最后一个窗口也被考虑进去。这不是漏掉了某些情况，而是确保所有情况都被正确处理。

虽然哈希表`cnt`会频繁地增加和减少元素的计数，但哈希表的平均时间复杂度为O(1)，因此从理论上讲，增减操作的性能是非常高效的。然而，在极端情况下（例如非常大的数组或极端的数据分布），频繁的操作可能导致性能下降。但在大多数实际应用中，使用哈希表来记录元素频率是有效且性能良好的方法。