题目：

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.

链接： 

题解：

用HashMap来保存(nums[i]，i) pair，假如存在相同key并且 i - map.get(key) <= k，返回true。否则遍历完毕以后返回false.

Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if(nums == null || nums.length == 0)            return false;        Map
     
       map = new HashMap<>();                for(int i = 0; i < nums.length; i++) {            if(map.containsKey(nums[i])) {                if(i - map.get(nums[i]) <= k)                    return true;            }             map.put(nums[i], i);        }                return false;    }}
     

 

二刷:

跟一刷一样，使用一个Map来保存数字以及数字的index，然后进行比较。假如相同并且 i - map.get(nums[i]) <= k，那么我们返回true。否则遍历完毕以后返回false.

Java:

Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if (nums == null || nums.length == 0) {            return false;        }        Map
     
       map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {            if (map.containsKey(nums[i]) && (i - map.get(nums[i]) <= k) ) {                return true;            }            map.put(nums[i], i);        }        return false;    }}
     

 

三刷：

方法还是和一刷，二刷一样，用一个HashMap来保存元素和位置。这里最好给HashMap设定一个初始的大小来避免resizing带来的cost。最大的test case好像是30000，我们设置30000 / 0.75 = 40000左右就可以了。

Java:

Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if (nums == null || k <= 0) {            return false;        }        Map
     
       map = new HashMap<>(41000);        for (int i = 0; i < nums.length; i++) {            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {                return true;            }            map.put(nums[i], i);        }        return false;    }}
     

 

使用Set以及sliding window。

1. 我们维护一个size为k的HashSet
2. 遍历整个数组，每次先判断是否有重复，有重复的话我们直接返回true
3. 当size > k的时候，这时候size() = k + 1。 我们要把距离当前元素最远的一个元素，即第i - k个元素移出set，继续维护set的size = k
4. 全部遍历完毕以后返回false。

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if (nums == null || k <= 0) {            return false;        }        Set
     
       set = new HashSet<>();        for (int i = 0; i < nums.length; i++) {            if (!set.add(nums[i])) {                return true;            }            if (set.size() > k) {                set.remove(nums[i - k]);            }        }        return false;    }}
     

 

Update:

利用HashMap的put。创建map的时候利用load factor = 0.75，我们建立一个比nums.length略大一些的map就能节约resizing的时间，但这也是空间换时间了。

 

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if (nums == null || k <= 0) return false;        Map
     
       map = new HashMap<>((int)(nums.length / 0.8));        for (int i = 0; i < nums.length; i++) {            if (!map.containsKey(nums[i])) map.put(nums[i], i);            else if (i - map.put(nums[i], i) <= k) return true;        }        return false;    }}
     

 

Update:重写了使用set的Sliding Window方法

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if (nums == null || k <= 0) return false;        Set
     
       set = new HashSet<>((int)(nums.length / 0.8));        for (int i = 0; i < nums.length; i++) {            if (!set.add(nums[i])) return true;            if (set.size() > k) set.remove(nums[i - k]);        }        return false;    }}
     

 

Update:  SouthPenguin的Sliding window方法。 最优解。

Worst case: Time Complexity - O(n)， Space Complexity - O(n)

public class Solution {    public boolean containsNearbyDuplicate(int[] nums, int k) {        if (nums == null || k <= 0) return false;        Set
     
       set = new HashSet<>((int)(nums.length / 0.8));        for (int i = 0; i < nums.length; i++) {            if (i > k) set.remove(nums[i - k - 1]);            if (!set.add(nums[i])) return true;        }        return false;    }}
     

 

 

 

 

Reference:

https://leetcode.com/discuss/38445/simple-java-solution