leetcode 220. Contains Duplicate III

佚名 5年前 (2019-04-07) 随笔 1541人围观抢沙发百度已收录

Compared with contains duplicate II, we should record a sorted set within the length k window.
So when we visit a new value, we can get the floor and ceiling of this value, if value - floor <= t or ceiling - value <= t, then return true.
And before the code we can have a review on some retrieve methods in NavigableSet

E lower(E e) means less than or null
E floor(E e) means less equal or null
E higher(E e) means bigger than or null
E ceiling(E e) means bigger equal or null

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> m = new TreeSet<>();
        int N = nums.length;
        for (int i = 0; i < N; ++i) {
            if (i > k) m.remove((long)nums[i - k - 1]);
            Long l = m.floor((long)nums[i]);
            if (l != null && nums[i] - l <= t) return true;
            Long h = m.ceiling((long)nums[i]);
            if (h != null && h - nums[i] <= t) return true;
            m.add((long)nums[i]);
        }
        return false;
    }
}