Contains Duplicate III

https://leetcode.com/problems/contains-duplicate-iii/description/

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

Thoughts

查任意长度为k的subarray是否包含两个元素的差<=t. brute force是维持长度为k的滑动窗口, 和一个set, 每次右移动, 检查Set中是否包含[num - t, num+t]中的任意一个数. TLE. [https://www.hrwhisper.me/leetcode-contains-duplicate-i-ii-iii/].

可以把set换成tree set存储和检查范围. 除此之外还可以用Buckts sort的思想, 把Set替换成一堆bucket, 每个bucket存范围在t + 1之间的数. 对于一个数, 将它分到第num / (t + 1)个桶中. 比如t =3, 那么[0, 1, 2, 3]存在0号bucket, [4, 5, 6, 7]存在1号桶, [8, 9, 10, 11]在2号桶 依次类推. 这里桶的范围是t+1以避免出现t=0时的情况. 现在对于num, 检查当前窗口中是否有范围在[num - t, num + t]内的元素, 如果有这么一个数, num2, 它可能是三种情况之一, 在同一个bucket(比如0, 3); num在bucket靠右, num2在bucket + 1的桶里(比如3, 7); num1靠左, num2在bucket - 1里(比如5, 1). 因此我们维护一个map, key作为bucket index, val为窗口中在该bucket的元素, 对元素, 不用set. 比如num = 5, 之前出现了8, 然后被10覆盖, 乍看上去5和10不在t中, 答案不对. 但当10出现时, 10和8就在同一个桶中, 已经查出来了, 所以不会出现错误.

Code

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

        Map<Long, Long> map = new HashMap<>();
        long div = (long)t + 1;
        for (int i = 0; i < nums.length; i++) {
            long num = (long)nums[i];
            long bucket = num / div;
            if (num < 0) {
                bucket--;
            }
            if (map.containsKey(bucket)
               || map.containsKey(bucket + 1) && map.get(bucket + 1) - num <= t
               || map.containsKey(bucket - 1) && num - map.get(bucket - 1) <= t) {
                return true;
            }
            if (i >= k) {
                map.remove((long)nums[i - k] / div);
            }
            map.put(bucket, num);
        }

        return false;
    }
}

Analysis

时间复杂度O(N).