220. Contains Duplicate III

,

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> windowTreeSet = new TreeSet<>(); // 窗口中的数值
        for (int i = 0; i < nums.length; i++) {
            // 因为题目要求 abs(i - j) <= k, 即窗口内最多 k 个元素，注意 nums[i] 不属于窗口内元素
            Integer floor = windowTreeSet.floor(nums[i]); // 小于等于 nums[i] 的最大元素，即最接近 nums[i] 的小值
            if (floor != null && nums[i] - (long) floor <= t) {
                return true;
            }
            Integer ceiling = windowTreeSet.ceiling(nums[i]); // 大于等于 nums[i] 的最小元素，即最接近 nums[i] 的大值
            if (ceiling != null && (long) ceiling - nums[i] <= t) {
                return true;
            }

            windowTreeSet.add(nums[i]); // 在此处入窗口的原因是便于上面获取获取 nums[i] 的相邻值，如果先入了窗口，则不能获取到相邻值
            if (i >= k) {
                windowTreeSet.remove(nums[i - k]); // 移除最左侧元素，为下一次循环做准备
            }
        }

        return false;
    }
}

Bucket Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int bucketSize = t + 1; // 因为题目要求 abs(nums[i] - nums[j]) <= t, 易知一个段内的数字数量为 t + 1

        // 每个桶仅存储一个值即可是因为若一个桶内存在了两个不同的值，那么我们可以直接返回 true, 所以一个桶仅需存储一个值
        // 注意该 map 仅存储窗口中的映射关系，窗口会保证 abs(i - j) <= k 条件得到满足
        Map<Integer, Integer> bucketIndexToValueMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int bucketIndex = getBucketIndex(nums[i], bucketSize);
            if (bucketIndexToValueMap.containsKey(bucketIndex)) {
                // 同一个桶内有值，直接返回
                return true;
            }

            Integer prevBucketValue = bucketIndexToValueMap.get(bucketIndex - 1);
            if (prevBucketValue != null && (long) nums[i] - prevBucketValue <= t) {
                return true;
            }
            Integer nextBucketValue = bucketIndexToValueMap.get(bucketIndex + 1);
            if (nextBucketValue != null && nextBucketValue - (long) nums[i] <= t) {
                return true;
            }

            bucketIndexToValueMap.put(bucketIndex, nums[i]); // 在此处将 nums[i] 加入窗口是为了便于同一个桶元素判断
            if (i >= k) {
                bucketIndexToValueMap.remove(getBucketIndex(nums[i - k], bucketSize));
            }
        }

        return false;
    }

    private int getBucketIndex(int num, int bucketSize) {
        if (num >= 0) {
            return num / bucketSize;
        } else {
            return (num + 1) / bucketSize - 1;
        }
    }
}

References

220. Contains Duplicate III
剑指 Offer II 057. 值和下标之差都在给定的范围内