AC java solution using subset


  • 3
    F
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    /*handle special case*/
        if(nums.length <= 1 || t < 0 || k < 1) {return false;}
        TreeSet<Long> set = new TreeSet<Long>();
        for(int i = 0; i < nums.length; i++){
            long min = Math.min((long)nums[i] - t,(long)nums[i] + t + 1);
            long max = Math.max((long)nums[i] - t, (long)nums[i] + t + 1);
        /*1.if the subset is not empty, means that we have the element that satisfy the requirement 
          2.if we cannot add the element to the set, that means we already have the element*/
            if(!set.subSet(min,max).isEmpty() || !set.add((long)nums[i])) {return true;}
            set.add((long)nums[i]);
            if(i >= k) {set.remove((long)nums[i - k]);}
        }
        return false;
    }
    

    }


  • 0
    F

    You are a genius!!!!


  • 0
    O

    why t must >= 0? thanks


  • 0
    O

    and if t >= 0, then I think we do not need to use Math.min and Math.max to get the min and max range, because nums[i] - t must < nums[i] + t + 1


Log in to reply
 

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