Java TreeSet solution


  • 0
    Y

    The idea is to maintain a window of size k + 1. Every time we add an item into the window, we compare it with its floor and ceiling.

        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            int n = nums.length;
            if (t < 0 || n <= 1 || k == 0) return false;        //!!!!
    
            TreeSet<Long> win = new TreeSet<>();
            // slide the window
            for (int i = 0; i < n; ++i) {
                long num = (long)nums[i];
                // remove nums[i - k]
                if (i >= k + 1) win.remove((long)nums[i - k - 1]);
    
                // add new number: nums[i]
                Long lo = win.floor(num);
                if (null != lo && num - lo <= t) return true;
                
                Long hi = win.ceiling(num);
                if (null != hi && hi - num <= t) return true;
                
                win.add(num);
            }
            return false;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.