求包含数组所有元素的最短子数组长度,现有思路为何通不过隐藏用例
你的思路存在的核心问题
- 首先存在明显的逻辑判断笔误:你写的判断条件
counter[start] > 1是错误的,counter存的是元素的出现次数,应该用counter[A[start]]取左边界对应元素的计数,哪怕你是笔误漏写了A[],还存在以下两个致命问题: - 没有提前统计原数组总共有多少个不同元素,也没有判断当前
[start, end]窗口内的不同元素数量是否已经覆盖全部唯一值,就直接收缩左边界,会导致你收缩后的窗口已经缺失了必要的唯一元素,仍然被你当作合法窗口计算长度。 - 收缩左边界时没有同步更新窗口内的唯一元素计数:当左边界元素的计数减到0时,意味着当前窗口已经不再包含该元素,唯一元素计数需要减1,此时必须停止收缩,你的逻辑完全没有这一步校验,会生成大量不符合要求的无效窗口。
反例验证
比如输入数组[3,1,2,1,2,3],原数组唯一元素共3个(3、1、2):
当end移动到下标3(元素为1)时,窗口范围是[0,3],元素为[3,1,2,1],此时counter[A[start]] = counter[3] = 1,不满足>1的条件,你不会收缩左边界。
当end移动到下标5(元素为3)时,counter[3] = 2,你开始收缩左边界,把下标0的3移出后,counter[3] = 1,此时窗口变成[1,5],你还会继续判断counter[A[1]] = counter[1] = 2,继续移出下标1的1,counter[1] = 1,窗口变成[2,5],此时窗口内元素是[2,1,2,3],你还会判断counter[A[2]] = counter[2] = 2,继续移出下标2的2,counter[2] = 1,窗口变成[3,5],元素为[1,2,3],长度3,这步看起来没问题,但如果数组是[3,3,1,2,1,2],你原逻辑的问题就会暴露:
当end移动到下标3(元素为2)时,已经集齐3个唯一元素,窗口长度是4,此时你判断counter[A[0]] = counter[3] = 2>1,就移出下标0的3,counter[3] =1,窗口变成[1,3],长度3,没问题。当end继续移动到下标4(元素为1),counter[1] = 2,你又开始收缩,此时counter[A[1]] = counter[3] = 1,你停止收缩,窗口是[1,4],长度4。但当end移动到下标5(元素为2),counter[2] = 2,你又开始收缩,此时counter[A[1]] = counter[3] =1,你停止收缩,窗口是[1,5],长度5。但此时你如果继续按照你的逻辑走,完全没有意识到如果把下标1的3移出,窗口就会丢失3这个唯一元素,后续如果没有新的3进来,你后面的所有窗口都是无效的,但你的逻辑不会做这个校验,会把后面的窗口长度当作合法值更新最短长度,导致结果错误。
正确实现步骤
- 先遍历一次数组,统计得到原数组的唯一元素总个数
total_unique - 初始化:左边界
start=0,窗口内唯一元素计数current_unique=0,计数数组counter长度为N、初始值全为0,最短长度初始为N(最坏情况整个数组才符合要求) - 遍历右边界
end从0到N-1:- 取当前元素
num = A[end],如果counter[num] == 0,说明该元素第一次进入窗口,current_unique +=1 counter[num] +=1- 只有当
current_unique == total_unique时,才可以收缩左边界:- 先计算当前窗口长度
end - start + 1,如果小于当前最短长度就更新最短长度 - 取左边界元素
left_num = A[start],counter[left_num] -=1 - 如果
counter[left_num] == 0,说明窗口已经丢失该唯一元素,current_unique -=1,停止收缩 start +=1
- 先计算当前窗口长度
- 取当前元素
- 最终输出最短长度即可
内容的提问来源于stack exchange,提问作者daniel

