Contains Duplicate III

• brute force，所有的sliding window中的元素，都要被check一次
• 如果array是sorted就好了，于是考虑利用BST作为数据结构，以获得更快的insert, search和delete
  • Self-balancing BST，因为操作的复杂度和树的高度直接相关

TreeSet

• TreeSet是有序的Set集合，因此支持add、remove、get等方法。
• 和NavigableSet一样，TreeSet的导航方法大致可以区分为两类，一类时提供元素项的导航方法，返回某个元素；另一类时提供集合的导航方法，返回某个集合。 lower、floor、ceiling 和 higher 分别返回小于、小于等于、大于等于、大于给定元素的最接近的元素，如果不存在这样的元素，则返回 null。
• 其中add, remove, contains方法复杂度为O(logn)

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]);
        // k is used as the size
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}