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

Solution

public class Solution {
       public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2 || k == 0 ||t<0)
            return false;

        int i = 0;

        TreeSet<Long> set = new TreeSet<>();
        for (int j = 0; j < nums.length; j++) {
            long cur = nums[j];
            long left = cur - t;
            long right = cur + t + 1;

            SortedSet sortedSet = set.subSet(left, right);
            if (!sortedSet.isEmpty()) {
                return true;
            }

            set.add(cur);
            if (set.size() >= k + 1) {
                set.remove((long)nums[i++]);
            }
        }

        return false;
    }
}