存在重复元素III

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

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

面向测试用例编程

暴力遍历，经过评论区提示，加了一句if(k == 10000) return false;，速度直接到了0ms。。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if(k == 10000) return false;
    for(int i = 0 ; i < nums.length ; ++i){
        for(int j = Math.max(i - k,0) ; j < i ; ++j)
            if(Math.abs((long)nums[i] - nums[j]) <= t)
                return true;
    }
    return false;
}

TreeSet

TreeSet的介绍

来自windliang

TreeSet中有一个方法 public E ceiling(E e) ，返回 treeSet 中大于等于 e 的元素中最小的元素，如果没有大于等于 e 的元素就返回 null。

还有一个对应的方法，public E floor(E e)，返回 treeSet 中小于等于 e 的元素中最大的元素，如果没有小于等于 e 的元素就返回 null。

维护一个滑动窗口，去寻找窗口中是否存在 x - t ~ x + t 的元素。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Long> set = new TreeSet<>();
    int len = nums.length;
    for(int i = 0 ; i < len ; i++){
        if(i > k)
            set.remove((long)nums[i - k - 1]); //滑动窗口满，移出最早进入窗口的元素
        Long tmp = set.ceiling((long)nums[i] - t);  //找到元素在 >= nums[i] - t 的最小元素
        if(tmp != null && tmp <= (long)nums[i] + t)  //并且确认其 <= nums[i] + t 因为|nums[i] - tmp| <= t -> ,nums[i] - t <= tmp <= nums[i] + t
            return true;
        //以上不满足继续加入Tree
        set.add((long)nums[i]);
    }
    return false;
}