题目描述

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。

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

样例

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

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

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

算法分析

滑动窗口 + 二分

• 1、当枚举到i位置时，滑动窗口存[i - k, i - 1]区间的值，因此可以确定滑动窗口内的元素j 与 i的差的绝对值也小于等于 ķ
• 2、在滑动窗口中寻找与nums[i]最接近的数，即找滑动窗口中小于等于nums[i]的最大值，找滑动窗口中大于等于nums[i]的最小值，若他们任何一个与nums[i]的差的绝对值小于等于t（原理：二分），则直接返回true
• 3、枚举完i位置后，需要将nums[i - k]位置的元素移除滑动窗口，将num[i]位置的元素加入到窗口

注意：此处用TreeSet来维护滑动窗口，因为floor(E x)可以找到小于等于e的最大值，ceiling(E x)可以找到大于等于e的最小值，并且TreeSet本身是排序好的

时间复杂度 $O(nlogk)$

Java 代码

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        if(n < 2) return false;
        TreeSet<Long> set = new TreeSet<Long>();
        for(int i = 0;i < n;i ++)
        {
            Long e = (long)nums[i];
            Long l = set.floor(e);//窗口中小于等于e的最大值
            Long r = set.ceiling(e);//窗口中大于等于e的最小值
            if(l != null && e - l <= t) return true;
            if(r != null && r - e <= t) return true;
            set.add(e);
            if(set.size() > k) set.remove((long)nums[i - k]);
        }
        return false;
    }
}