219. Contains Duplicate II

题目：

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.

链接： http://leetcode.com/problems/contains-duplicate-ii/

题解：

用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<Integer, Integer> 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<Integer, Integer> 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<Integer, Integer> 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。

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

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || k <= 0) {
            return false;
        }
        Set<Integer> 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<Integer, Integer> 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<Integer> 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<Integer> 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