# 220. Contains Duplicate III

&#x20;[**220. Contains Duplicate III**](https://leetcode.com/problems/contains-duplicate-iii/description/)

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
```

**Example 2:**

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

**Example 3:**

```
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
```

***My Solutions：***

方法1：brute force

```
        for(int i = 0; i < nums.length-1; i++) {
            for(int j = i + 1; j < nums.length && j <= i + k; j++) {
                if(Math.abs((long)(nums[i])-nums[j]) <= t) return true;
            }
        }
        return false;
```

方法2：

对于数组内的一个整数，如果能方便的求出大于它的最小整数和小于它的最大整数，那么我们就可以判断差值是否大于`t`。能方便的求出最大下限和最小上限，最先想到的数据结构是二叉搜索树BST，因为左孩子就是最大下限，右孩子就是最小上限。

可以用一个大小为k的滑动窗口，将窗口内的元素组织成一个BST，每次向前滑动一步，添加一个新元素，同时删除一个最老的元素，如此不断向前滑动，不断更新BST。如果BST内部有两个元素差值大于`t`，则返回true，如果直到扫描完数组，BST里都没有出现差值大于k的两个数，则返回false。

对于BST数据结构，可以用现成的，C++里是`multiset`，Java里是`TreeSet`。

TreeSet数据结构（Java）使用红黑树实现，是平衡二叉树的一种。

该数据结构支持如下操作：

1\. floor()方法返set中≤给定元素的最大元素；如果不存在这样的元素，则返回 null。

2\. ceiling()方法返回set中≥给定元素的最小元素；如果不存在这样的元素，则返回 null。

e.g. \[0,1,2,3,4], 对2来说，floor是1，ceiling是3

复杂度: O(nlgn)

```
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        
        if (k < 1 || t < 0) return false;
        
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            
            if ((set.floor(x) != null && x <= set.floor(x) + t) 
                || (set.ceiling(x) != null && x >= set.ceiling(x) - t)) {
                return true;
            }
            
            set.add(x); //将此element加入bst
            
            if (i >= k) set.remove(nums[i - k]); //把最先加入set的数删去
        }
        return false;
    }
}
```
