题目描述

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

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

样例

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

算法1

(平衡二叉树) $O(n·logk)$

* 滑动窗口：在窗口里找到离当前元素最近的 大于等于这个元素的值和小于等于这个元素的值
* 利用TreeSet中的ceiling和floor方法，可在logn的时间复杂度内进行元素的查找，插入和删除。
* ceiling：第一个大于等于x的节点(后继节点)，找不到返回null
* floor：第一个小于等于x的节点(前驱节点)，找不到返回null
* 流程：遍历每个节点，如果能找到满足条件的前驱和后继，则直接返回true
    * 如果不满足条件，则插入元素，如果set满了则删除最开始添加的元素，维护窗口长度为k
* 注意：如果窗口内有重复元素，则直接返回true，不会有集合判重的问题

Java 代码

class Solution {
    //如果窗口内有重复元素，则直接返回true，不会有集合判重的问题
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for(int i = 0; i < nums.length; i++){
            long x = (long)nums[i];
            Long prev = set.floor(x);
            if(prev != null && x-prev <= t) return true;
            Long next = set.ceiling(x);
            if(next != null && next-x <= t) return true;
            set.add(x);
            if(set.size() > k) set.remove((long)nums[i-k]);
        }
        return false;
    }
}