图解 | 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 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！
面试题】即可获取
好文分享给更多人↓↓评论