# 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/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/hash-table/contains-duplicate-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.