存在重复元素3

220. 存在重复元素 III

难度中等331

给你一个整数数组 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 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 104
• 0 <= t <= 2^31 - 1

有序集合+滑动窗口

滑动窗口维护一个长度为k的区域,有序集合快速查找集合中与当前数字最相近的那个数字（这个查找过程的时间复杂度是O(log(n)）

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<>();

        for(int i=0;i<n;i++){
            // 查找下界元素
            Long lv = set.floor((long)nums[i]);
            // 查找上界元素
            Long gv = set.ceiling((long)nums[i]);
			// 如果下界满足差值小于等于t
            if(lv!=null&&Math.abs(lv - nums[i])<=t){
                return true;
            }
            // 如果上界满足差值小于等于t
            if(gv!=null&&Math.abs(gv - nums[i])<=t){
                return true;
            }
            // 向集合中插入当前元素
            set.add((long) nums[i]);
            // 如果当前窗口中的元素的数量大于k那么需要删除最先加入的元素
            if(set.size()>k){
                set.remove((long)nums[i-k]);
            }
        }
        return false;
    }
}

桶排序

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<Long, Long>();
        long w = (long) t + 1;
        for (int i = 0; i < n; i++) {
            long id = getID(nums[i], w);
            if (map.containsKey(id)) {
                return true;
            }
            if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                return true;
            }
            map.put(id, (long) nums[i]);
            if (i >= k) {
                map.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }

    public long getID(long x, long w) {
        if (x >= 0) {
            return x / w;
        }
        return (x + 1) / w - 1;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信