# Contains Duplicate III

## Solution

### TreeSet (Binary Search Tree)

```java
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < nums.length; ++i) {
        // Find the successor of current element
        Integer s = set.ceiling(nums[i]);
        if (s != null && s <= nums[i] + t) return true;

        // Find the predecessor of current element
        Integer g = set.floor(nums[i]);
        if (g != null && nums[i] <= g + t) return true;

        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}
```

要注意一个test case：

BST solution is incorrect in following case:

```
[-1, 2147483647]
1
2147483647
```

### Using Buckets

20 ms, faster than 89.87%

> Inspired by bucket sort, we can achieve linear time complexity in our problem using buckets as window.

主要思想是将nums\[]里的数字用`t` 作为宽度`diff`，分成若干bucket，这样每个`nums[i]`会对应bucket有一个编号，当下次循环`nums[i]`所对应的bucket id在buckets不为空，则说明之前有一个数字也被分配到了那个bucket，这样就来check那个数与当前nums\[i]是否相差在`t`之内。

buckets的元素的数目保持在k个，相当于保持滑动窗口。

`Map<Long, Long> buckets = new HashMap<>();`

buckets存入bucket id到nums\[i]的映射

另外要避免t = 0，作为分母，可以将diff = (long) t + 1;

用`((long) num - (long) min) / diff;`

减去min更好地均摊

```java
class Solution {
    private long getBucketIndex(int num, int t, int min, long diff) {
        return ((long) num - (long) min) / diff;
    }
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0 || k < 0 || t < 0) {
            return false;
        }
        Map<Long, Long> buckets = new HashMap<>();

        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            min = Math.min(num, min);
        }
        long diff = (long) t + 1;

        for (int i = 0; i < nums.length; i++) {
            long index = getBucketIndex(nums[i], t, min, diff);

            if (buckets.containsKey(index)) {
                return true;
            }

            if (buckets.containsKey(index - 1) && Math.abs(nums[i] - buckets.get(index - 1)) < diff) {
                return true;
            }

            if (buckets.containsKey(index + 1) && Math.abs(nums[i] - buckets.get(index + 1)) < diff) {
                return true;
            }

            buckets.put(index, (long) nums[i]);
            if (i >= k) {
                buckets.remove(getBucketIndex(nums[i - k], t, min, diff));
            }
        }
        return false;
    }
}
```

[https://www.laioffer.com/en/videos/2018-07-23-220-contains-duplicate-3/](https://www.laioffer.com/en/videos/2018-07-23-220-contains-duplicate-3/)
