220. Contains Duplicate III 发表于 2022-01-20 Sliding Window1234567891011121314151617181920212223class 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 Sort1234567891011121314151617181920212223242526272829303132333435363738394041class 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; } }} Reference220. Contains Duplicate III剑指 Offer II 057. 值和下标之差都在给定的范围内