@@ -0,0 +1,1381 @@
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * Given an array of integers, find out whether there are two distinct indices i and j in the array such that the%0A * difference between nums%5Bi%5D and nums%5Bj%5D is at most t and the difference between i and j is at most k.%0A *%0A * Tags: Binary Search Tree%0A *%0A * Similar Problems: (E) Contains Duplicate, (E) Contains Duplicate II%0A */%0Apublic class ContainsDuplicate3 %7B%0A    private long getBucketId(long i, long w) %7B%0A        return i %3C 0 ? (i + 1) / w - 1 : i / w;%0A    %7D%0A%0A    /**%0A     * O(n) Time, O(n) Space%0A     */%0A    public boolean containsNearbyAlmostDuplicate(int%5B%5D nums, int k, int t) %7B%0A        if (t %3C 0) return false;%0A        Map%3CLong, Long%3E bucketMap = new HashMap%3C%3E();%0A        long width = (long)t + 1;%0A        for (int i = 0; i %3C nums.length; ++i) %7B%0A            long id = getBucketId(nums%5Bi%5D, width);%0A            if (bucketMap.containsKey(id))%0A                return true;%0A            if (bucketMap.containsKey(id - 1) && Math.abs(nums%5Bi%5D - bucketMap.get(id - 1)) %3C width)%0A                return true;%0A            if (bucketMap.containsKey(id + 1) && Math.abs(nums%5Bi%5D - bucketMap.get(id + 1)) %3C width)%0A                return true;%0A            bucketMap.put(id, (long)nums%5Bi%5D);%0A            if (i %3E= k)%0A                bucketMap.remove(getBucketId(nums%5Bi - k%5D, width)); // out of window%0A        %7D%0A        return false;%0A    %7D%0A%7D%0A

add 220 Contains Duplicate 3