220. Contains Duplicate III

Question

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Solution

保证indexd的差在一定范围内，用sliding window. 保证window中两个元素的差<=t，考虑以下两种方法：

方法一：利用TreeSet的数据结构，使用.floor(n)方法返回小于n的元素中的最大者，如果不存在则返回null，使用.ceiling(n)方法返回大于n的元素中的最小者，如果不存在则返回null。然后看当前元素nums[i]和这两个元素的差是否小于t，只要有一个小于就返回true。这里要注意的是，两个int的数相加或者相减很可能overflow，因此要将其转化为long再做比较。

方法二：利用bucket sort的思想，将每个num放到不同的bucket中去，然后只要比较当前的bucket以及前后的bucket就可以了，具体推导方法如下：

如果： | nums[i] - nums[j] | <= t 式a

等价： | nums[i] / t - nums[j] / t | <= 1 式b

推出： | floor(nums[i] / t) - floor(nums[j] / t) | <= 1 式c

​等价： floor(nums[j] / t) ∈ {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d

那么对于每一个num,只要key = num / t，然后搜寻(key-1, key, key + 1)是否在维护的最大size为k的map中，并且判断真实的value diff是否<= t就可以了。

在这里要注意两点：

1）我们将通式key = num/t变为key = num / Math.max(1,t)是为了应对当t为0时的情况，虽然这时的key会和t=1时相同，但是在后面判断真实的value diff是否<= t时依然可以根据t的真实值进行判断。

2）因为要搜寻key-1,key+1，因此当key为边界情况时可能造成overflow，因此要将map中的key转换成long进行存储，同时因为涉及到要判断真实的value diff是否<= t，这时也有可能出现overflow的情况，因此value也要转换成long进行存储。

代码如下：

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        if (k < 1 || t < 0) {
            return false;
        }

        //TreeSet version
        // long diff = t;
        // TreeSet<Integer> set = new TreeSet<>();
        // for (int i = 0; i < nums.length; i++) {
        //     int curt = nums[i];
        //     if ((set.floor(curt) != null && curt <= diff + set.floor(curt)) || (set.ceiling(curt) != null && set.ceiling(curt)  <= diff + curt)) {
        //         return true;
        //     }
        //     set.add(curt);
        //     if (i >= k) {
        //         set.remove(nums[i - k]);
        //     }
        // }

        //Bucket version
        HashMap<Long, Long> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                int removeElement = nums[i - k - 1];
                long key = getId(removeElement, t);
                map.remove(key);
            }

            int curt = nums[i];
            long curtKey = getId(curt, t);
            if (map.containsKey(curtKey) && Math.abs(map.get(curtKey) - nums[i]) <= t) {
                return true;
            }
            if (map.containsKey(curtKey - 1) && Math.abs(map.get(curtKey - 1) - nums[i]) <= t) {
                return true;
            }
            if (map.containsKey(curtKey + 1) && Math.abs(map.get(curtKey + 1) - nums[i]) <= t) {
                return true;
            }
            map.put(curtKey, (long)curt);
        }

        return false;
    }

    private long getId(int n, int t) {
        return (long)n / Math.max(1, t);
    }
}