217. Contains Duplicate

题目大意是判读数组里是否有重复的数，有就返回true，没有返回false。题目很简单就用了O(N)时间的解法，HashSet的查找插入的平均时间复杂度都是O(1)，而BST查找插入的平均时间复杂度都是O(logN)，所以选择用了HashSet，其他解法就是先排序再比较也是ok的。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean containsDuplicate(int[] nums) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>(n);
        for(int t : nums) {
            if (set.contains(t)) return true;
            set.add(t);
        } 
        return false;
    }
}

219. Contains Duplicate II

题目大意是给定一个数组和一个整数k，判断数组中是否存在两个相等的数，且他们下标差值不大于k，存在返回true，不存在返回false。
暴力解法直接两个for循环比较，时间复杂度O(N²)，能通过需要325ms，所以可以根据上一题的思路利用HashMap，key存放数组中的值，value存放下标。代码如下：

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

时间复杂度为O(N), 通过只用了8ms，效率提升很明显。

  1. Contains Duplicate III
    上一题是数组两个值相等，这一题变成数组两个值相差最大不超过t，下标差不超过k，网上说暴力破解不行，我试了一下发现还是能通过的，唯一坑的地方在于int必须要转成long，不然好几个测试用例都会溢出通不过。
1
2
3
4
5
6
7
8
9
10
11
12
13
 public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    int n = nums.length;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            //System.out.println();
            if(Math.abs(((long)nums[i] - (long)nums[j])) <= t && Math.abs(i - j) <= k) {
                return true;
            }
        }
        
    }
    return false;
}

下面来看看利用平衡树时间复杂度为O(NlogN)的解法，这个解法利用了滑动窗口+TreeSet，我觉得很巧妙，首先TreeSet里面保证存放的是下标差值满足条件的数值，这就利用了滑动窗口每次新加入一个值的时候再剔除掉最边界的值，这样只需判断TreeSet中两个值的差值。在判断数值差值的时候用了数学的方式，|a-b| <= t，那么 b-t<= a <= b+t，于是可以先在TreeSet里找到一个满足大于等于nums[i]-t的最小值，然后再判断这个最小值是否小于等于nums[i]+t就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if(k<=0) return false;
    TreeSet<Long> set = new TreeSet<Long>();
    int n = nums.length;
    for(int i=0; i<n; i++) {
        Long x = set.ceiling((long)nums[i]-(long)t);
       if(x != null && x <= (long)nums[i] + (long)t) return true;
        if(i>=k) {
            set.remove((long)nums[i-k]);
        }
        set.add((long)nums[i]);
    }
    return false;
}

这里面每次要注意溢出的情况，所以都把int转成long。这题还有一个利用bucket（桶）时间复杂度只有O(N)的解法，理解起来还有点困难，暂时先把解法贴出来，希望可以有人讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if(k <= 0 || t < 0) return false;
    HashMap<Long, Long> keyToNum = new HashMap<>();
    long div = (long)t + 1;
    for (int i = 0; i < nums.length; i++) {
        long num = (long)nums[i];
        long key = num / div;
        if(num < 0) key--;
        if (keyToNum.containsKey(key)
                || keyToNum.containsKey(key + 1) && keyToNum.get(key + 1) - num <= t
                || keyToNum.containsKey(key - 1) && num - keyToNum.get(key - 1) <= t)
            return true;
        if (i >= k) keyToNum.remove(((long)nums[i - k]) / div);
        keyToNum.put(key, num);
    }
    return false;
}