Array - 220. Contains Duplicate III

220、 Contains Duplicate III

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

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

思路：

这道题是217和219的变形题，题意是说有一个整数数组，如果数组中有两个数的差在t内，并且这两个数的索引之差在k内，就返回true否则返回false。

1. 使用暴力求解的时间复杂度是O(N*K)，空间复杂度为O(1)。
2. 使用BST来记录位置的和值可以把时间复杂度优化到O(N*logk)，但是额外使用了map所以空间复杂度为O(k)。
3. 使用bucket的思想和BST来查找最接近的值与当前值的差值，时间复杂度可以为O(n)，空间的复杂度与bucket的size有关，最差就是对每一个数字都建立一个bucket。

代码：

java：

class Solution {

  /*public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        if (nums == null || nums.length == 0 || k <= 0 || t <0) return false;
        
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long ceil = set.ceiling((long)nums[i] - t);
            Long floor = set.floor((long)nums[i] + t);
            
            if ((floor != null && floor >= nums[i]) || (ceil != null && ceil <= nums[i])) {
                return true;
            }
            
            set.add((long)nums[i]);
            if (i >= k) {
                set.remove((long)nums[i-k]);
            }
        }
        
        return false;
    }*/
    
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) return false;
        Map<Long, Long> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
            long bucket = remappedNum / ((long) t + 1);
            if (map.containsKey(bucket)
                    || (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t)
                        || (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
                            return true;
            if (map.entrySet().size() >= k) {
                long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
                map.remove(lastBucket);
            }
            map.put(bucket, remappedNum);
        }
        return false;
    }
}