找出最长等值子数组

You are given a 0-indexed integer array nums and an integer k.

A subarray is called equal if all of its elements are equal. Note that the empty subarray is an equal subarray.

Return the length of the longest possible equal subarray after deleting at most k elements from nums.

A subarray is a contiguous, possibly empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,3,2,3,1,3], k = 3
Output: 3
Explanation: It's optimal to delete the elements at index 2 and index 4.
After deleting them, nums becomes equal to [1, 3, 3, 3].
The longest equal subarray starts at i = 1 and ends at j = 3 with length equal to 3.
It can be proven that no longer equal subarrays can be created.

Example 2:

Input: nums = [1,1,2,2,1,1], k = 2
Output: 4
Explanation: It's optimal to delete the elements at index 2 and index 3.
After deleting them, nums becomes equal to [1, 1, 1, 1].
The array itself is an equal subarray, so the answer is 4.
It can be proven that no longer equal subarrays can be created.

 

Constraints:

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

/*
 * 题目思路：
 * 1. 使用滑动窗口的方法来找到最长的等值子数组。
 * 2. 使用Java Stream API来处理数组中的频率统计和窗口移动。
 * 3. 计算需要删除的元素数量，如果超过k则移动left指针，直到删除的元素数量小于等于k。
 * 4. 记录并更新最大等值子数组的长度。
 */

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int longestEqualSubarray(int[] nums, int k) {
        Map<Integer, Long> countMap = new HashMap<>();
        int maxFreq = 0;
        int maxLength = 0;
        int left = 0;

        for (int right = 0; right < nums.length; right++) {
            countMap.put(nums[right], countMap.getOrDefault(nums[right], 0L) + 1);
            maxFreq = countMap.values().stream().mapToInt(Long::intValue).max().orElse(0);

            if (right - left + 1 - maxFreq > k) {
                countMap.put(nums[left], countMap.get(nums[left]) - 1);
                left++;
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

这个题解的基本思路是使用一个哈希表（通过defaultdict实现）来存储数组中每个元素的所有索引。接着，对于哈希表中的每个元素，使用一个滑动窗口的方法来找到包含最多k个非该元素的最长子数组。具体来说，哈希表的键是元素值，值是该元素在数组中出现的所有位置的索引列表。然后，对于每个键值对，使用双指针技术（滑动窗口）来计算在最多删除k个其他元素的条件下，可以形成的最长等值子数组的长度。

O(n^2)

O(n)