目录

一、需求

二、HashMap实现

2.1  思路分析

2.2  代码实现

2.3  复杂度分析

三、滑动窗口算法

3.1  思路分析

3.2  代码实现

3.3  复杂度分析

四、参考地址

---

一、需求

      A:给定一个整数数组和一个整数k，判断数组中是否存在两个不同的索引i和j，使得nums[i]=nums[j];

      B:而且i和j的差的绝对值最大为k;

二、HashMap实现

2.1  思路分析

      A:先找是否存在相同的元素，又是查找，又是索引，很明显是HashMap;

      B:存在相同的元素的话，判断下标差值绝对值k的关系，只要有小于等于k的就返回true;

2.2  代码实现

public boolean containsNearbyDuplicate(int[] nums, int k) {//创建HashMap对象HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();//遍历数组for(int i =0; i < nums.length; i++) {if(hm.containsKey(nums[i])) {if(Math.abs(hm.get(nums[i])-i) <= k) {return true;} else {hm.remove(nums[i]);hm.put(nums[i],i);}} else {hm.put(nums[i],i);}}return false;
}

2.3  复杂度分析

      A:时间复杂度为O(n);

      B:空间复杂度为O(n);

三、滑动窗口算法

3.1  思路分析

3.2  代码实现

public boolean containsNearbyDuplicate(int[] nums, int k) {//创建HashSet集合HashSet<Integer> hs = new HashSet<Integer>();//遍历数组for(int i = 0; i < nums.length; i++) {if(hs.containsKey(nums[i])) {return true;}hs.put(nums[i]);//过滤掉数值相同但不符合绝对值条件的if(hs.size() > k) {hs.remove()}}
}

3.3  复杂度分析

      A:时间复杂度为O(n);

      B:空间复杂度为O(min(n,k));

四、参考地址

LeetCode官方题解:https://leetcode-cn.com/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode/