图解 | LeetCode #219 存在重复元素||

👇👇关注后回复 “进群” ，拉你进程序员交流群👇👇

作者丨微木

来源丨编程狂想曲

你好，我是微木。

今天分享的内容是LeetCode中219.存在重复元素|| 简单 这个题目。

题目描述：

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值至多为 k。

示例:

输入: nums = [1,2,3,1,2,3], k = 2

输出: false

思路分析
根据题目描述，有两点需要思考：
一是nums[i]=nums[j]。
要判断数组中有没有重复值，可以对数组进行遍历。对于每一个要考察的元素，先判断HashSet中有没有该元素。有，则找到了重复元素；没有，则将当前考察元素存入HashSet。这里为什么用HashSet，文末分析。
二是两个不同的索引i和j的差的绝对值至多为k。
拿示例nums = [1,2,3,1,2,3], k = 2来说，前三个元素是1、2、3，当考察到元素3时，此时，元素3对应的索引为2，元素1对应的索引为0，两者之差的绝对值为2等于k=2。
这时，要继续考察下一个元素1，则第一个元素1就不在考察范围内了。因为，如果第一个元素1还在考察范围内的话，虽然找到了两个一样的元素1，但它两的索引差值是3大于k=2。
这说明什么呢？说明，要在一个窗口内寻找有没有相等的元素。
经过上述分析，该题目的的解题方法是滑动窗口和Set相结合来求解。
具体代码实现如下：
对于上述代码实现，有两点说明一下：
为什么窗口内最多能容纳k+1个元素？
对于示例nums = [1,2,3,1,2,3], k = 2。先将前三个元素，即k+1个元素存入set。动画演示如下：
在将前3个元素存入set后，下一个待考察元素是1，它的索引是3，其值和索引为0的元素1是相等的。但，它两之间索引的差值为3-0=3，大于k=2，因此，set中最多容纳k+1个元素。

为什么从set中移除元素时，移除的是nums[i-k]这个元素？
上述分析了为什么set中最多容纳k+1个元素。对于示例nums = [1,2,3,1,2,3], k = 2来说，当set中已经有k+1等于3个元素时，为了继续考察下一个元素，就需要将滑动窗口左侧的元素移除，即nums[i-k]=nums[2-2]=nums[0]这个元素需要从窗口左侧移除。i代表当前考察的元素对应的索引。
在上述的代码实现中，用的是HashSet来判断窗口内是否有重复元素。那么，能不能用LinkedList和ArrayList呢？
用LinkedList时，代码实现如下：
提交后提示超时，为什么呢？原因在于，LinkedList是用链表实现的，在链表中查找一个元素是否存在时，要遍历整个链表，增加了时间复杂度。
用ArrayList时，代码实现如下：
提交后同样提示超时，为什么呢？原因在于，ArrayList是用数组实现的，每次为了保证窗口内的元素最多为k+1个，在移除第一个元素后，后面的元素都有向前移动一个位置，增加了时间复杂度。

-End-

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！

点击👆卡片，关注后回复【面试题】即可获取

在看点这里好文分享给更多人↓↓