leetcode 219 Contains Duplicate II
z
 2017-12-25 09:53:42  

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 absolute difference between i and j is at most k.

1.

最intuitive的方法是一个二重循环来判断，但这样势必时间复杂很高，导致超时：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for(int i=1; i<nums.length; i++){
            for(int j=Math.max(i-k,0); j<i;j++){
                if(nums[i] == nums[j]){
                    return true;
                }
            }
        }
        return false;
    }
}

2.

使用之前返回两个相等的数的下标那种方法：

利用一个HashMap保存当前数和索引：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++){
            if(m.containsKey(nums[i])){
                if(i-m.get(nums[i])<=k){
                    return true;
                }
            }
            m.put(nums[i], i);
        }
        return false;
    }
}

3.

使用一个set，利用set.add()来判断当前加进set中的数字是否已经存在于set中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> s = new HashSet<Integer>();
        for(int i=0;i<nums.length; i++){
            if(i>k){
                s.remove(nums[i-k-1]);
            }
            if(!s.add(nums[i])){
                return true;
            }
        }
        return false;
    }
}

注意边界条件的设定。