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.

Solution:

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> ts = new TreeSet<>();
        for(int i=0; i<nums.length; i++){
            Long floor = ts.floor((long)nums[i]);
            Long ceiling = ts.ceiling((long)nums[i]);
            if((floor!=null && Math.abs(nums[i]-floor)<=t)
                || (ceiling!=null && Math.abs(nums[i]-ceiling)<=t)) return true;
            ts.add((long)nums[i]);
            if(i>=k) ts.remove((long)nums[i-k]);
        }
        return false;
    }
}
comments powered by Disqus