class Solution {
public:
int maxSubarrayLength(vector<int>& nums, int k) {
}
};
2958. 最多 K 个重复元素的最长子数组
给你一个整数数组 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 <= 1051 <= nums[i] <= 1091 <= k <= nums.length原站题解
python3 解法, 执行用时: 540 ms, 内存消耗: 31.3 MB, 提交时间: 2023-12-11 00:29:23
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
ans = left = 0
cnt = Counter()
for right, x in enumerate(nums):
cnt[x] += 1
while cnt[x] > k:
cnt[nums[left]] -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
java 解法, 执行用时: 57 ms, 内存消耗: 57.1 MB, 提交时间: 2023-12-11 00:29:11
class Solution {
public int maxSubarrayLength(int[] nums, int k) {
int ans = 0, left = 0;
Map<Integer, Integer> cnt = new HashMap<>();
for (int right = 0; right < nums.length; right++) {
cnt.merge(nums[right], 1, Integer::sum);
while (cnt.get(nums[right]) > k) {
cnt.merge(nums[left++], -1, Integer::sum);
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
cpp 解法, 执行用时: 236 ms, 内存消耗: 141.6 MB, 提交时间: 2023-12-11 00:28:58
class Solution {
public:
int maxSubarrayLength(vector<int> &nums, int k) {
int ans = 0, left = 0;
unordered_map<int, int> cnt;
for (int right = 0; right < nums.size(); right++) {
cnt[nums[right]]++;
while (cnt[nums[right]] > k) {
cnt[nums[left++]]--;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};
golang 解法, 执行用时: 192 ms, 内存消耗: 17.6 MB, 提交时间: 2023-12-11 00:28:46
func maxSubarrayLength(nums []int, k int) (ans int) {
cnt := map[int]int{}
left := 0
for right, x := range nums {
cnt[x]++
for cnt[x] > k {
cnt[nums[left]]--
left++
}
ans = max(ans, right-left+1)
}
return
}