找出最长等值子数组

难度: 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⁵
1 <= nums[i] <= nums.length
0 <= k <= nums.length

Submission

运行时间: 311 ms

内存: 36.6 MB

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        D = defaultdict(list)
        for i in range(len(nums)):
            D[nums[i]].append(i)
        res = 0
        for x in D.keys():
            d = D[x]
            if len(d) <= res: continue
            j = 0
            for i in range(len(d)):
                if d[i]-d[j]+1 - (i-j+1) > k:
                    j+= 1
                res = max(res, i - j + 1)
        return res

Explain

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

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        D = defaultdict(list) # 创建一个默认字典，用于存储每个元素及其对应的索引列表
        for i in range(len(nums)): # 遍历数组，填充字典
            D[nums[i]].append(i)
        res = 0 # 初始化结果变量
        for x in D.keys(): # 遍历字典的每个键
            d = D[x] # 获取当前元素的索引列表
            if len(d) <= res: continue # 如果当前元素的出现次数小于或等于已找到的最长长度，则跳过
            j = 0 # 初始化滑动窗口的起始指针
            for i in range(len(d)): # 遍历索引列表
                while d[i]-d[j]+1 - (i-j+1) > k: # 如果当前窗口内非x元素的数量超过k，则移动起始指针
                    j += 1
                res = max(res, i - j + 1) # 更新最长等值子数组的长度
        return res # 返回结果

Explore

哈希表（或字典）提供高效的查找和插入操作，平均时间复杂度为O(1)。使用哈希表可以快速访问任何元素的所有索引，这对于算法中频繁的元素查找和索引访问非常有用。相比之下，如果使用数组或链表，查找特定值的所有出现或其索引可能需要O(n)的时间复杂度，这会显著增加算法的总体运行时间。因此，哈希表是一种更优的数据结构选择。

在滑动窗口实现中，维护两个指针i和j，分别代表窗口的结束和开始位置。通过遍历索引列表，指针i逐步向右移动，扩大窗口。当窗口中非当前元素的数量超过k时（计算方法是窗口长度减去窗口中当前元素的数量，即d[i]-d[j]+1 - (i-j+1)），开始移动指针j以缩小窗口，直到非当前元素的数量不超过k为止。这种方法确保了每次计算窗口长度时，窗口内最多包含k个非当前元素。

`max(res, i - j + 1)`这个表达式用于更新并保持最长等值子数组的最大长度。这里，`i - j + 1`计算的是当前考虑的等值子数组的长度，从索引j到i。每次遍历新的索引i时，都会用当前子数组的长度与之前记录的最大长度res进行比较，并更新res为两者之间的较大值。这确保了res始终保持为遍历过程中遇到的最长等值子数组的长度。

如果某个元素的出现次数较少，那么其索引列表长度较小，这对算法的效率是有利的。因为对于这些元素，滑动窗口操作需要处理的数据量减少，从而减少了计算量。然而，如果数组中大部分元素都是这种情况，那么虽然单个元素处理速度快，但需要处理的元素种类可能很多，从而增加总的处理时间。总体来说，算法的效率与数组中元素的分布和重复情况有关，索引列表较短通常有助于提高效率。