Contains Duplicate III

Solution

TreeSet (Binary Search Tree)

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < nums.length; ++i) {
        // Find the successor of current element
        Integer s = set.ceiling(nums[i]);
        if (s != null && s <= nums[i] + t) return true;

        // Find the predecessor of current element
        Integer g = set.floor(nums[i]);
        if (g != null && nums[i] <= g + t) return true;

        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

要注意一个test case：

BST solution is incorrect in following case:

[-1, 2147483647]
1
2147483647

Using Buckets

20 ms, faster than 89.87%

Inspired by bucket sort, we can achieve linear time complexity in our problem using buckets as window.

主要思想是将nums[]里的数字用t 作为宽度diff，分成若干bucket，这样每个nums[i]会对应bucket有一个编号，当下次循环nums[i]所对应的bucket id在buckets不为空，则说明之前有一个数字也被分配到了那个bucket，这样就来check那个数与当前nums[i]是否相差在t之内。

buckets的元素的数目保持在k个，相当于保持滑动窗口。

Map<Long, Long> buckets = new HashMap<>();

buckets存入bucket id到nums[i]的映射

另外要避免t = 0，作为分母，可以将diff = (long) t + 1;

用((long) num - (long) min) / diff;

减去min更好地均摊

class Solution {
    private long getBucketIndex(int num, int t, int min, long diff) {
        return ((long) num - (long) min) / diff;
    }
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0 || k < 0 || t < 0) {
            return false;
        }
        Map<Long, Long> buckets = new HashMap<>();

        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            min = Math.min(num, min);
        }
        long diff = (long) t + 1;

        for (int i = 0; i < nums.length; i++) {
            long index = getBucketIndex(nums[i], t, min, diff);

            if (buckets.containsKey(index)) {
                return true;
            }

            if (buckets.containsKey(index - 1) && Math.abs(nums[i] - buckets.get(index - 1)) < diff) {
                return true;
            }

            if (buckets.containsKey(index + 1) && Math.abs(nums[i] - buckets.get(index + 1)) < diff) {
                return true;
            }

            buckets.put(index, (long) nums[i]);
            if (i >= k) {
                buckets.remove(getBucketIndex(nums[i - k], t, min, diff));
            }
        }
        return false;
    }
}

https://www.laioffer.com/en/videos/2018-07-23-220-contains-duplicate-3/