Contains Duplicate III

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.

思路：

　　二分查找树

我的代码：

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums==null || nums.length==0 || k<=0)    return false;
        
        TreeSet<Integer> tree = new TreeSet<Integer>();
        
        for(int i=0; i<nums.length; i++)
        {
            Integer floor = tree.floor(nums[i]+t);
            Integer ceil = tree.ceiling(nums[i]-t);
            if((floor!=null && floor>=nums[i]) || (ceil!=null && ceil<=nums[i])) return true;
            tree.add(nums[i]);
            if(i >= k) tree.remove(nums[i-k]);
        }
        return false;
    }
}

学习之处：

• 之前没注意到java中还有TreeSet这样一个集合，实现的机理是红黑树，所以查找和删除的时间复杂度O(logk)，该API在查找和删除上有巨大的优势啊。在涉及到查找历史数据问题的时候，考虑到此
• 该题的思路是维持一个大小为k的二分查找树