LeetCode 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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

注意题目中一旦出现，当两者距离at most k等constraint时，都可以考虑使用sliding window的方法，每次仅保留window size=k的元素，判断完后再移动并更新window。

思路一：naive thinking
考虑排序，但排序时也得带上index，即需要记录排序前各个元素原先的下标。排序后，check数组中是否存在符合at most t & at most k的元素。

思路二：基于sliding window
顺序扫描数组，每次仅保存size=k的滑动窗口，并用TreeSet或bucket存储窗口中现有的元素，加入新元素后判断是否与集合中元素满足difference<=t的条件。注意窗口的更新，如何维护treeset或bucket（加入新元素的同时，删除最早加入的元素）。

这里要注意为什么需要使用treeset与bucket，而不是queue？原因是treeset和bucket具有根据input value快速查找的能力，若新加入的元素为nums[i]，
则treeset可以通过floor与ceiling在O(log k)的时间复杂度下查找最相近的元素。

Long floor = set.floor((long) nums[i]);     
Long ceiling = set.ceiling((long) nums[i]);

bucket可以在O(1)时间复杂度下查找，原因是将出入分成了大小为t+1的桶，这里类似于hashmap，可以根据输入大小nums[i]直接反查在哪个桶中。

long remappedNum = (long) nums[i] - Integer.MIN_VALUE; 
long bucket = remappedNum / ((long) t + 1);

基于treeset的代码如下

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // Deal with corner cases
        if (k <= 0 || nums.length < 2) {
            return false;
        }
        
        TreeSet<Long> set = new TreeSet<>();
        // Scan using sliding window
        int i = 0;
        while (i < nums.length) {
            Long floor = set.floor((long) nums[i]);
            Long ceiling = set.ceiling((long) nums[i]);
            
            if (floor != null && nums[i] - floor <= t ||
                ceiling != null && ceiling - nums[i] <= t)
                    return true;
            
            if (i >= k) {
                set.remove((long) nums[i-k]);
            }
            set.add((long) nums[i++]);
        }
        return false;
    }
}

参考：
https://discuss.leetcode.com/topic/15191/java-o-n-lg-k-solution/13