我给大家分享 LeetCode 算法题，主要都是挑选那些很可能在面试中出现的题，或者可能出现类似的题，多看看这些题至少能够在面试中不那么被动。
上次给大家分享过一次LeetCode 算法 | 数组中有重复元素吗？今天给大家分享的 LeetCode 算法题还和数组中重复元素相关，一起来看一看。
题目：
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。
示例1：
输入: nums = [1,2,3,1], k = 3 输出: true
示例2：
输入: nums = [1,0,1,1], k = 1 输出: true
示例3：
输入: nums = [1,2,3,1,2,3], k = 2 输出: false
这道题，分享两种方法给大家。
1. 直接法
看到这道题，很多人的第一反应就是我挨个比较不就行了吗？首先都跟第一个元素比较，然后再第二轮，将后面的元素和第二个比较，在这过程中，只要满足题目要求，就返回 true，看下代码：
public boolean containsNearbyDuplicate(int[] nums, int k) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] == nums[j]) { if (j - i <= k) { return true; } } } } return false; }
这种方式时间复杂度会很高，因为有两层循环，那么我们可否考虑不用两层循环呢？答案是肯定的。
2. 使用 HashMap
为什么可以使用 HashMap 呢？还记得之前我分享的一篇文章吗？LeetCode 算法 | 两数之和不简单啊，这里面有 HashMap 来处理和的问题，我在这也套用一下。
使用 num[i] 作为 key，索引的位置 i 作为 value，每次根据 num[i] 的值来获取 i，并计算间隔，如下：
public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); int inter = 0; for(int i = 0; i < nums.length; i++) { if(map.containsKey(nums[i])) { inter = i - map.get(nums[i]); if(inter <= k) { return true; } // 更新key为nums[i]的位置 map.put(nums[i], i); } else { map.put(nums[i], i); } } return false; }
所以我们巧妙的运用 HashMap 可以将算法复杂度降低到 O(n)。
OK，这道算法题，就分享这么多，希望能对大家有所启发。如果你有其他思路，也欢迎留言。我建了个 LeetCode 算法交流群，大家在下方可以加我微信，我拉你进群，共同学习交流。
