What is the main pattern for solving Find the Longest Equal Subarray?

The problem relies on array scanning combined with hash-based index tracking for each unique value, enabling efficient window evaluation.

Can the subarray be empty?

Yes, an empty subarray counts as an equal subarray, but typically the maximum length is achieved with at least one element.

How do we efficiently handle large arrays?

Use hash maps to store indices for each number and sliding windows on these lists, which avoids repeatedly scanning the full array.

Does the order of elements matter after deletion?

Yes, deletions must maintain the original order to form contiguous equal subarrays.

What happens if k is larger than necessary?

Extra deletions beyond what is needed to form the longest equal subarray have no effect; the maximum length is still constrained by existing sequences.

#2831

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。如果子数组中所有元素都相等，则认为子数组是一个等值子数组。注意，空数组是等值子数组。从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。子数组是数组中一个连续且可能为空的元素序列。示例 1：输入：…

数组哈希表二分查找滑动窗口

题目描述

给你一个下标从 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

lightbulb

解题思路

方法一：哈希表 + 双指针

我们用双指针维护一个单调变长的窗口，用哈希表维护窗口中每个元素出现的次数。

窗口中的所有元素个数减去窗口中出现次数最多的元素个数，就是窗口中需要删除的元素个数。

每一次，我们将右指针指向的元素加入窗口，然后更新哈希表，同时更新窗口中出现次数最多的元素个数。当窗口中需要删除的元素个数超过了 $k$ 时，我们就移动一次左指针，然后更新哈希表。

遍历结束后，返回出现次数最多的元素个数即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def longestEqualSubarray(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        l = 0
        mx = 0
        for r, x in enumerate(nums):
            cnt[x] += 1
            mx = max(mx, cnt[x])
            if r - l + 1 - mx > k:
                cnt[nums[l]] -= 1
                l += 1
        return mx

speed

复杂度分析

指标	值
时间	complexity depends on the number of unique values and their occurrences, roughly O(n) to build maps and slide windows. Space complexity is O(n) for storing index lists of each unique element.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Watch for off-by-one errors when counting deletions within the sliding window.
question_mark
Expect discussion about mapping values to index lists for efficient lookups.
question_mark
Be prepared to explain why contiguous windows capture maximum equal subarrays after deletions.

warning

常见陷阱

外企场景

error
Forgetting to account for deletions at the edges of the window, leading to underestimated lengths.
error
Attempting to scan the original array repeatedly instead of using precomputed index lists.
error
Ignoring cases where multiple disjoint subarrays of the same value compete for maximum length.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Instead of deleting up to k elements, allow swapping k elements to maximize the equal subarray.
arrow_right_alt
Return the actual subarray, not just its length, after optimal deletions.
arrow_right_alt
Apply the same logic to 2D grids to find the longest equal row or column segment after removing k elements.

help

常见问题

外企场景

继续练习

#3134 找出唯一性数组的中位数 #2009 使数组连续的最少操作数 #2830 销售利润最大化