My Java O(n) AC solution using TreeSet


  • 0
    D

    My thought: Only keep the window size k, all elements during this k elements in the set.
    if t == 0, means nums[i] == nums[j], so just check whether set contains the duplicate number.
    if t != 0, means nums[j] should be in the range: nums[i]-t ~ nums[i] + t, here should check the + and - whether exceeds Integer limitation, so use long type.
    Check whether there is valid number in the number range in the set, we can use TreeSet ceiling and floor, the ceiling should less than big, the floor should bigger than small.

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { 
            if (k < 1 || t < 0) { 
                return false; 
            } 
            TreeSet<Long> set = new TreeSet<>(); 
            for (int i = 0; i <nums.length; ++i) { 
                if (i > k) { 
                    set.remove((long)nums[i-k-1]); 
                } 
                if (t == 0) { 
                    if (!set.add((long)nums[i])) { 
                        return true; 
                    } 
                } else { 
                    long small = (long)nums[i] - (long)t; 
                    long big = (long)nums[i] + (long)t; 
                    long from = small; 
                    long to = big; 
                    if (small > big) { 
                        from = big; 
                        to = small; 
                    } 
                    if (set.ceiling(from) != null && set.floor(to) != null && 
                        set.ceiling(from) <= to && set.floor(to) >= from) { 
                        return true; 
                    } 
                    set.add((long)nums[i]); 
                } 
            } 
            return false; 
        }
    

Log in to reply
 

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