本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。给你一个整数数组nums和一个整数k。一个元素x在数组中的频率指的是它在数组中的出现次数。如果一个数组中所有元素的频率都小于等于k那么我们称这个数组是好数组。请你返回nums中最长好子数组的长度。子数组指的是一个数组中一段连续非空的元素序列。示例 1输入nums[1,2,3,1,2,3,1,2],k2输出6解释最长好子数组是[1,2,3,1,2,3]值12和3在子数组中的频率都没有超过 k2。[2,3,1,2,3,1]和[3,1,2,3,1,2]也是好子数组。 最长好子数组的长度为6。示例 2输入nums[1,2,1,2,1,2,1,2],k1输出2解释最长好子数组是[1,2]值1和2在子数组中的频率都没有超过 k1。[2,1]也是好子数组。 最长好子数组的长度为2。示例 3输入nums[5,5,5,5,5,5,5],k4输出4解释最长好子数组是[5,5,5,5]值5在子数组中的频率没有超过 k4。 最长好子数组的长度为4。提示1 nums.length 10^51 nums[i] 10^91 k nums.length解法 不定长滑窗求最长但越短越容易合法对于本题新加入元素x n u m s [ r i g h t ] xnums[right]xnums[right]后如果x xx的出现次数超过k kk则不断右移左指针 left直到窗口内的x xx的出现次数等于k kk为止然后用窗口大小r i g h t − l e f t 1 right−left1right−left1更新答案的最大值。classSolution{publicintmaxSubarrayLength(int[]nums,intk){intans0;intleft0;MapInteger,IntegercntnewHashMap();for(intright0;rightnums.length;right){cnt.merge(nums[right],1,Integer::sum);// cnt[nums[right]]while(cnt.get(nums[right])k){cnt.merge(nums[left],-1,Integer::sum);// cnt[nums[left]]--left;}ansMath.max(ans,right-left1);}returnans;}}classSolution{public:intmaxSubarrayLength(vectorintnums,intk){intans0,left0;unordered_mapint,intcnt;for(intright0;rightnums.size();right){cnt[nums[right]];while(cnt[nums[right]]k){cnt[nums[left]]--;left;}ansmax(ans,right-left1);}returnans;}};classSolution:defmaxSubarrayLength(self,nums:List[int],k:int)-int:ansleft0cntdefaultdict(int)forright,xinenumerate(nums):cnt[x]1whilecnt[x]k:cnt[nums[left]]-1left1ansmax(ans,right-left1)returnansfuncmaxSubarrayLength(nums[]int,kint)(ansint){cnt:map[int]int{}left:0forright,x:rangenums{cnt[x]forcnt[x]k{cnt[nums[left]]--left}ansmax(ans,right-left1)}return}复杂度分析时间复杂度O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)。