企业官网建设流程全解析

LeetCode 219：存在重复元素 II

一、推荐先做入门的 217

我之前做过 217「存在重复元素」。

这道题算是入门的，用于理解怎么使用哈希表中的set。链接是这个

当时 217 只需要判断：

当前数字以前有没有出现过？

所以一个set就够了。

例如：

seen=set()

每次扫描当前数字时：

以前见过 → True 以前没见过 → 加入 seen

但 219 又多了一个条件：

两个相同元素的下标之差必须小于等于 k。

也就是说，这道题不只是问：

这个数字以前有没有出现过？

还要继续问：

它上一次出现在哪里？

所以只用set已经不够了。

因为set只能告诉我有没有，却不能告诉我在哪里。

这时候就自然而然地想到了哈希表中的另外一种形式：

dict

二、哈希表里到底应该保存什么？

既然题目最后要比较：

两个相同数字之间的下标距离

那么字典最自然可以保存：

数字 → 下标

例如：

1 → 3 2 → 5 4 → 7

表示：

数字 1 出现在下标 3 数字 2 出现在下标 5 数字 4 出现在下标 7

于是当我扫描到当前：

nums[i]

时，如果这个数字以前出现过，就可以直接拿出之前保存的下标，计算：

i-groups[num]

然后判断：

<= k

就可以了。

不过这里很容易出现一个新的问题：

如果同一个数字出现很多次，那dict里的 key 不就重复了吗？

三、同一个数字出现很多次，key 怎么办？

比如：

nums = [1, ..., 1, ..., 1]

数字1可能出现在：

下标 0 下标 5 下标 7

那字典是不是要变成：

1 → 0 1 → 5 1 → 7

？其实不行。

因为字典里的：

key

是不能重复的。

如果已经有：

groups[1]=0

后面又写：

groups[1]=5

并不会出现两个：

1

而是会直接把原来的 value 覆盖掉：

原来：1 → 0 重新赋值以后：1 → 5

也就是说：

相同 key 再次赋值时，会更新这个 key 对应的 value。

那这里新的问题就来了：

我们到底应不应该覆盖旧下标？

答案是：应该。

而且这正好是这道题真正关键的地方。

四、为什么要保存“最近一次出现的位置”？

还是看刚才这个例子。

数字1分别出现在：

下标 0 下标 5 下标 7

假设：

k = 3

第一次扫描到下标0：

1 → 0

先记录下来。

之后扫描到下标5。

因为1已经在字典里面，所以计算：

5 - 0 = 5

大于：

3

所以现在还不能返回True。

那这时候要不要继续保留：

1 → 0

？

如果一直保留下标0，等之后扫描到下标7时：

7 - 0 = 7

还是不满足。

但实际上：

7 - 5 = 2

已经满足：

<= 3

所以在扫描到下标5时，虽然这一次还不能返回True，但应该把：

1 → 0

更新成：

1 → 5

这样后面来到下标7时，比较的就是：

7 - 5 = 2

于是就能正确找到答案。

所以这里字典真正应该保存的并不是：

数字 → 第一次出现的位置

而是：

数字 → 最近一次出现的位置

五、为什么只保存“最近一次”就够了？

这里还可以继续想一步。

假设当前下标是：

i

同一个数字以前出现过很多次：

p1 < p2 < p3 < ... < i

那么离当前i最近的，一定是：

最后一次出现的位置

也就是最大的那个下标。

比如：

以前出现的位置： 0 5 8 现在的位置：10

那么距离分别是：

10 - 0 = 10 10 - 5 = 5 10 - 8 = 2

最近的一定是：

8

所以如果连：

i - 最近一次出现的位置

都已经大于k，那么更早的位置只会离得更远，更不可能满足要求。

也就是说：

最近一次都不行 ↓ 更早的更不可能行

因此：

对于每个数字，只保留最近一次出现的位置就够了。

而dict相同 key 重新赋值时会覆盖旧 value 的特性，在这里反而正好符合我们的需求。

每次都可以：

groups[num]=i

让它始终保存：

num → 最新下标

六、按照这个思路，我一开始写出的代码

想清楚这一点以后，我一开始写的是：

classSolution:defcontainsNearbyDuplicate(self,nums:list[int],k:int)->bool:groups={}fori,numinenumerate(nums):ifnumnotingroups:groups[num]=ielse:ifabs(groups[num]-i)<=k:returnTrueelse:groups[num]=ireturnFalse

整个过程就是：

扫描当前数字 ↓ 以前没出现过 → 记录当前下标 以前出现过 ↓ 拿出之前保存的下标 ↓ 计算两个位置之间的距离 ↓ 距离 <= k → True 距离 > k ↓ 旧位置已经没有继续保留的必要 ↓ 更新成当前位置

这套逻辑本身是可以的。

七、这里其实不需要 abs()

我一开始写的是：

abs(groups[num]-i)

但后来发现这里其实不需要abs()。

因为我们一直按照：

从左到右

扫描数组。

以前保存的位置一定是在当前i的左边。

也就是说：

groups[num] <= i

所以：

i-groups[num]

一定不会是负数。

因此可以直接写：

i-groups[num]

而不需要：

abs(groups[num]-i)

八、代码还能继续简化

再看一遍我原来的写法：

ifnumnotingroups:groups[num]=ielse:ifgroups[num]和 i 的距离<=k:returnTrueelse:groups[num]=i

这里其实有重复。

因为：

第一次出现时

要做：

groups[num]=i

以前出现过，但是距离太远时

最后还是要做：

groups[num]=i

也就是说，只要没有：

returnTrue

当前下标最终都应该成为：

这个数字最近一次出现的位置

所以：

groups[num]=i

完全可以统一放到最后。

于是原来的：

没出现过 → 保存 出现过但距离太远 → 更新

可以合并成：

只要这一次没有找到答案 → 一律把当前位置保存成最新位置

这样代码就会简单很多。

九、最后代码

classSolution:defcontainsNearbyDuplicate(self,nums:list[int],k:int)->bool:groups={}fori,numinenumerate(nums):ifnumingroupsandi-groups[num]<=k:returnTruegroups[num]=ireturnFalse

整个过程现在可以压缩成：

扫描当前数字 ↓ 这个数字以前出现过？ ↓ 有 → 看当前下标和最近一次出现位置的距离 ↓ 距离 <= k → True 否则 ↓ groups[num] = i ↓ 把当前位置更新成这个数字最新的位置

这里：

groups[num]=i

虽然只有一行，但其实同时处理了两种情况：

第一次出现 → 新增一个 key-value 已经出现过 → 用当前下标覆盖旧 value

最终groups始终保持：

数字 → 最近一次出现的下标

十、这道题和前面的哈希表题有什么关系？

这道题让我进一步理解：

dict 的 value 不只是“随便保存一个下标”。

具体保存什么，要看题目真正需要什么信息。

比如：

LC 242 有效的字母异位词 字符 → 出现次数

LC 1 两数之和 数字 → 下标

而这道 219 是：

数字 → 最近一次出现的下标

这里“最近一次”非常重要。

因为题目关心的是：

相同数字之间的最近距离

而且这道题也让我更清楚dict中重复 key 的处理方式：

key 不会重复保存 ↓ 再次给同一个 key 赋值 ↓ 原来的 value 会被覆盖

有些情况下，“覆盖”可能意味着丢失信息。

但在这道题里：

覆盖旧位置恰好就是我们需要做的事情，因为旧位置没有最近一次的位置更有价值。