Medium

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 k。

如果一个子数组中的所有元素都相等，则称该子数组为 相等子数组。注意，空子数组也是相等子数组。

返回在从 nums 中删除最多 k 个元素后，可能的最长相等子数组的长度。

子数组是数组中一个连续的可能为空的元素序列。

示例 1：

输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优方案是删除下标 2 和下标 4 的元素。
删除后，nums 变为 [1, 3, 3, 3]。
最长相等子数组从 i = 1 开始到 j = 3 结束，长度等于 3。
可以证明无法创建更长的相等子数组。

示例 2：

输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优方案是删除下标 2 和下标 3 的元素。
删除后，nums 变为 [1, 1, 1, 1]。
数组本身就是一个相等子数组，所以答案是 4。
可以证明无法创建更长的相等子数组。

提示：

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

解题思路

解题思路

这道题的关键洞察是：要形成最长的相等子数组，我们需要选择某个特定的数值，然后在包含这个数值的所有位置中选择一个连续的区间，使得删除区间内其他数值后剩余的相等元素最多。

核心思想

  1. 按数值分组：首先将数组中相同数值的所有下标收集起来，存储在哈希表中。

  2. 滑动窗口：对于每个数值的下标列表，使用滑动窗口找到最优的区间。关键是理解：如果我们选择下标列表中从位置 i 到位置 j 的区间，那么原数组中对应的区间是 [indices[i], indices[j]]，其中包含 indices[j] - indices[i] + 1 个元素，但只有 j - i + 1 个是我们想要的数值，所以需要删除 (indices[j] - indices[i] + 1) - (j - i + 1) = indices[j] - indices[i] - (j - i) 个元素。

  3. 约束条件：我们需要保证删除的元素数量不超过 k，即 indices[j] - indices[i] - (j - i) <= k。

  4. 窗口调整：当删除元素数量超过 k 时，收缩左边界；否则扩展右边界，并更新最大长度。

这种方法的时间复杂度是 O(n)，空间复杂度是 O(n)，是最优解法。

代码实现

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> pos;
        
        // 收集每个数值的所有位置
        for (int i = 0; i < nums.size(); i++) {
            pos[nums[i]].push_back(i);
        }
        
        int maxLen = 0;
        
        // 对每个数值使用滑动窗口
        for (auto& [val, indices] : pos) {
            int left = 0;
            for (int right = 0; right < indices.size(); right++) {
                // 当前窗口需要删除的元素数量
                while (indices[right] - indices[left] - (right - left) > k) {
                    left++;
                }
                maxLen = max(maxLen, right - left + 1);
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        
        pos = defaultdict(list)
        
        # 收集每个数值的所有位置
        for i, num in enumerate(nums):
            pos[num].append(i)
        
        max_len = 0
        
        # 对每个数值使用滑动窗口
        for indices in pos.values():
            left = 0
            for right in range(len(indices)):
                # 当前窗口需要删除的元素数量
                while indices[right] - indices[left] - (right - left) > k:
                    left += 1
                max_len = max(max_len, right - left + 1)
        
        return max_len

public class Solution {
    public int LongestEqualSubarray(IList<int> nums, int k) {
        var pos = new Dictionary<int, List<int>>();
        
        // 收集每个数值的所有位置
        for (int i = 0; i < nums.Count; i++) {
            if (!pos.ContainsKey(nums[i])) {
                pos[nums[i]] = new List<int>();
            }
            pos[nums[i]].Add(i);
        }
        
        int maxLen = 0;
        
        // 对每个数值使用滑动窗口
        foreach (var indices in pos.Values) {
            int left = 0;
            for (int right = 0; right < indices.Count; right++) {
                // 当前窗口需要删除的元素数量
                while (indices[right] - indices[left] - (right - left) > k) {
                    left++;
                }
                maxLen = Math.Max(maxLen, right - left + 1);
            }
        }
        
        return maxLen;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var longestEqualSubarray = function(nums, k) {
    const pos = new Map();
    
    // 收集每个数值的所有位置
    for (let i = 0; i < nums.length; i++) {
        if (!pos.has(nums[i])) {
            pos.set(nums[i], []);
        }
        pos.get(nums[i]).push(i);
    }
    
    let maxLen = 0;
    
    // 对每个数值使用滑动窗口
    for (const indices of pos.values()) {
        let left = 0;
        for (let right = 0; right < indices.length; right++) {
            // 当前窗口需要删除的元素数量
            while (indices[right] - indices[left] - (right - left) > k) {
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(n)

时间复杂度：O(n)，其中 n 是数组长度。需要遍历数组一次收集位置信息，然后对每个数值的位置列表进行滑动窗口操作，总的遍历次数不超过 n。

空间复杂度：O(n)，用于存储每个数值对应的位置列表。