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 在这个子数组中都至多出现 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 在这个子数组中都至多出现 1 次。注意 [2,1] 也是好子数组。
可以证明没有长度大于 2 的好子数组。

示例 3：

输入：nums = [5,5,5,5,5,5,5], k = 4
输出：4
解释：最长的好子数组是 [5,5,5,5]，因为值 5 在这个子数组中出现 4 次。
可以证明没有长度大于 4 的好子数组。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

解题思路

这是一道典型的滑动窗口问题。我们需要找到最长的子数组，使得其中每个元素的频率都不超过 k。

解题思路：

使用滑动窗口（双指针）技术：

  1. 维护一个哈希表记录当前窗口内每个元素的频率
  2. 使用左右两个指针 left 和 right 表示窗口边界
  3. 右指针不断向右移动扩大窗口，同时更新元素频率
  4. 当某个元素的频率超过 k 时，移动左指针缩小窗口，直到所有元素频率都不超过 k
  5. 在每次移动过程中记录最大的合法窗口长度

算法步骤：

  • 初始化左指针 left = 0，哈希表 count 和结果 maxLen = 0
  • 右指针 right 从 0 遍历到数组末尾：
    • 将 nums[right] 加入窗口，更新其频率
    • 如果 nums[right] 的频率超过 k，则移动左指针直到频率恢复合法
    • 更新最大长度：maxLen = max(maxLen, right - left + 1)

这个方法的核心在于巧妙地使用滑动窗口维护一个始终满足条件的子数组，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            count[nums[right]]++;
            
            while (count[nums[right]] > k) {
                count[nums[left]]--;
                if (count[nums[left]] == 0) {
                    count.erase(nums[left]);
                }
                left++;
            }
            
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        count = {}
        left = 0
        max_len = 0
        
        for right in range(len(nums)):
            count[nums[right]] = count.get(nums[right], 0) + 1
            
            while count[nums[right]] > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            
            max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int MaxSubarrayLength(int[] nums, int k) {
        var count = new Dictionary<int, int>();
        int left = 0, maxLen = 0;
        
        for (int right = 0; right < nums.Length; right++) {
            if (count.ContainsKey(nums[right])) {
                count[nums[right]]++;
            } else {
                count[nums[right]] = 1;
            }
            
            while (count[nums[right]] > k) {
                count[nums[left]]--;
                if (count[nums[left]] == 0) {
                    count.Remove(nums[left]);
                }
                left++;
            }
            
            maxLen = Math.Max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

var maxSubarrayLength = function(nums, k) {
    let left = 0;
    let maxLen = 0;
    let freq = new Map();
    
    for (let right = 0; right < nums.length; right++) {
        freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
        
        while (freq.get(nums[right]) > k) {
            freq.set(nums[left], freq.get(nums[left]) - 1);
            left++;
        }
        
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被访问两次（加入和移出窗口各一次）
空间复杂度O(min(n, m))哈希表最多存储 min(n, m) 个不同元素，其中 m 是数组中不同元素的个数

相关题目