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

You are given an integer array nums and an integer k.

The frequency of an element x is the number of times it occurs in an array.

An array is called good if the frequency of each element in this array is less than or equal to k.

Return the length of the longest good subarray of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,2,3,1,2,3,1,2], k = 2
Output: 6
Explanation: The longest possible good subarray is [1,2,3,1,2,3] since the values 1, 2, and 3 occur at most twice in this subarray. Note that the subarrays [2,3,1,2,3,1] and [3,1,2,3,1,2] are also good.
It can be shown that there are no good subarrays with length more than 6.

Example 2:

Input: nums = [1,2,1,2,1,2,1,2], k = 1
Output: 2
Explanation: The longest possible good subarray is [1,2] since the values 1 and 2 occur at most once in this subarray. Note that the subarray [2,1] is also good.
It can be shown that there are no good subarrays with length more than 2.

Example 3:

Input: nums = [5,5,5,5,5,5,5], k = 4
Output: 4
Explanation: The longest possible good subarray is [5,5,5,5] since the value 5 occurs 4 times in this subarray.
It can be shown that there are no good subarrays with length more than 4.

 

Constraints:

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

/* 
 * 思路：使用滑动窗口算法和Java Stream API。 
 * 我们维护一个窗口，并使用哈希表记录当前窗口内每个元素的频率。 
 * 如果某个元素的频率超过k，则移动窗口的左端以缩小窗口，直到所有元素频率都<=k。 
 * 在这个过程中，记录窗口的最大长度。
 */ 
import java.util.HashMap; 
import java.util.Map; 
import java.util.stream.IntStream; 

public class Solution { 
    public int longestGoodSubarray(int[] nums, int k) { 
        Map<Integer, Integer> count = new HashMap<>(); 
        int[] result = {0}; 
        IntStream.range(0, nums.length).forEach(right -> { 
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1); 
            while (count.get(nums[right]) > k) { 
                count.put(nums[result[0]], count.get(nums[result[0]]) - 1); 
                result[0]++; 
            } 
            result[0] = Math.max(result[0], right - result[0] + 1); 
        }); 
        return result[0]; 
    } 
}

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

O(n)

O(n)