220. 存在重复元素 III

难度困难666

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

提示：

• 0 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 104
• 0 <= t <= 231 - 1

滑动窗口+二分法

题解：https://leetcode.cn/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/

class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {int n = nums.length;//使用TreeSet，快速找到 小于等于x的最大值floor 或 小于等于x的最小值ceilingTreeSet set = new TreeSet<>();for(int i = 0; i < n; i++){Long num = nums[i] * 1L;Long l = set.floor(num); //找到小于等于num的最大值Long r = set.ceiling(num); // 找到大于等于num的最小值if(l != null && num-l <= valueDiff) return true;if(r != null && r-num <= valueDiff) return true;set.add(num);// 一个窗口内不可能存在两个大小相同的数，所以可以直接删除// 假设两个数下标是i和j(i < j),当遍历到j时，就会直接返回true了if(i >= indexDiff) set.remove(nums[i-indexDiff]*1L);}return false;}
}// 到i位置检查i-k位置上的元素是否满足要求，超时
// class Solution {
//     public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
//         Set set = new HashSet<>();
//         Map map = new HashMap<>();//nums[i] i
//         for(int i = 0; i < nums.length; i++){
//             if(i > indexDiff) set.remove(nums[i-indexDiff-1]);
//             for(int key : set){
//                 if(Math.abs(nums[i]-key) <= valueDiff && Math.abs(map.get(key) - i) <= indexDiff){
//                     return true;
//                 }
//             }
//             set.add(nums[i]);
//             map.put(nums[i],i);
//         }
//         return false;
//     }
// }

桶排序

题解：https://leetcode.cn/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/

上述解法无法做到线性的原因是：我们需要在大小为 k 的滑动窗口所在的「有序集合」中找到与 u 接近的数。

如果我们能够将 k 个数字分到 k 个桶的话，那么我们就能 O(1) 的复杂度确定是否有 [u - t, u + t]的数字（检查目标桶是否有元素）。

具体的做法为：令桶的大小为 size=t+1size = t + 1size=t+1，根据 u 计算所在桶编号：

• 如果已经存在该桶，说明前面已有 [u - t, u + t]范围的数字，返回 true
• 如果不存在该桶，则检查相邻两个桶的元素是有 [u - t, u + t] 范围的数字，如有 返回 true
• 建立目标桶，并删除下标范围不在 [max(0, i - k), i) 内的桶

class Solution {long size;public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n = nums.length;Map map = new HashMap<>();size = t + 1L;for (int i = 0; i < n; i++) {long u = nums[i] * 1L;long idx = getIdx(u);// 目标桶已存在（桶不为空），说明前面已有 [u - t, u + t] 范围的数字if (map.containsKey(idx)) return true;// 检查相邻的桶long l = idx - 1, r = idx + 1;if (map.containsKey(l) && u - map.get(l) <= t) return true;if (map.containsKey(r) && map.get(r) - u <= t) return true;// 建立目标桶map.put(idx, u);// 移除下标范围不在 [max(0, i - k), i) 内的桶if (i >= k) map.remove(getIdx(nums[i - k] * 1L));}return false;}long getIdx(long u) {return u >= 0 ? u / size : ((u + 1) / size) - 1;}
}

getIdx部分的解释：宫水三叶