题目
给你一个整数数组 nums 和一个整数 k 。
一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。
如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。
请你返回 nums 中 最长好 子数组的长度。
子数组 指的是一个数组中一段连续非空的元素序列。
示例 1：
1
2
3
4
| 输入：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：
1
2
3
4
| 输入：nums = [1,2,1,2,1,2,1,2], k = 1
输出：2
解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
最长好子数组的长度为 2 。
|
示例 3：
1
2
3
4
| 输入：nums = [5,5,5,5,5,5,5], k = 4
输出：4
解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
最长好子数组的长度为 4 。
|
提示：
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= nums.length
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int ans=0;
int n=nums.length;
HashMap<Integer,Integer> map = new HashMap<>();
for(int left=0,right=0;right<n;right++){
map.merge(nums[right],1,Integer::sum);
while(map.get(nums[right])>k){
map.merge(nums[left],-1,Integer::sum);
if(map.get(nums[left])==0){
map.remove(nums[left]);
}
left++;
}
ans=Math.max(ans,right-left+1);
}
return ans;
}
}
|
知识点
简单题，只需使用哈希表和滑动窗口。
