What is the key idea behind Length of Longest Subarray With at Most K Frequency?

Use a sliding window combined with a hash map to track how many times each element occurs, shrinking the window when any count exceeds k.

Can this problem be solved without a hash map?

No efficient linear solution exists without tracking element counts, since you need to know if adding a new element exceeds k.

What happens when k = 1?

The algorithm reduces to finding the longest subarray with all unique elements, shrinking the window whenever a duplicate appears.

Is it necessary to check the frequency of all elements at every step?

No, only the newly added element's frequency needs checking, and the window shrinks until all counts are valid.

Does the array scanning plus hash lookup pattern apply to variations of this problem?

Yes, any problem that tracks element frequencies in a contiguous window benefits from this exact sliding window with hash map pattern.

#2958

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个整数数组 nums 和一个整数 k 。一个元素 x 在数组中的频率指的是它在数组中的出现次数。如果一个数组中所有元素的频率都小于等于 k ，那么我们称这个数组是好数组。请你返回 nums 中最长好子数组的长度。子数组指的是一个数组中一段连续非空的元素序列。示例 1：…

数组哈希表滑动窗口

题目描述

给你一个整数数组 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 <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= nums.length

lightbulb

解题思路

方法一：双指针

我们可以用两个指针 $j$ 和 $i$ 分别表示子数组的左右端点，初始时两个指针都指向数组的第一个元素。

接下来，我们遍历数组 $nums$ 中的每个元素 $x$ ，对于每个元素 $x$ ，我们将 $x$ 的出现次数加一，然后判断当前子数组是否满足要求。如果当前子数组不满足要求，我们就将指针 $j$ 右移一位，并将 $nums[j]$ 的出现次数减一，直到当前子数组满足要求为止。然后我们更新答案 $ans = \max(ans, i - j + 1)$ 。继续遍历，直到 $i$ 到达数组的末尾。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        cnt = defaultdict(int)
        ans = j = 0
        for i, x in enumerate(nums):
            cnt[x] += 1
            while cnt[x] > k:
                cnt[nums[j]] -= 1
                j += 1
            ans = max(ans, i - j + 1)
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(N) because each element is added and removed from the hash map at most once. Space complexity is O(N) to store the frequency map in the worst case when all elements are unique.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Are you correctly updating the frequency map when moving both left and right pointers?
question_mark
Can you handle arrays where elements repeat more than k times immediately?
question_mark
Have you considered edge cases like k = 1 or uniform arrays?

warning

常见陷阱

外企场景

error
Forgetting to decrement counts when shrinking the window leads to incorrect frequency tracking.
error
Assuming all elements can be included without checking frequency can overcount the window length.
error
Not handling subarrays at array boundaries can miss the maximum length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the length of the longest subarray where exactly k occurrences of any element are allowed.
arrow_right_alt
Compute the longest subarray with at most k distinct elements rather than frequency-based restriction.
arrow_right_alt
Determine the maximum sum subarray where each number appears at most k times.

help

常见问题

外企场景

继续练习

#2935 找出强数对的最大异或值 II #2932 找出强数对的最大异或值 I #3013 将数组分成最小总代价的子数组 II