本文共 2306 字，大约阅读时间需要 7 分钟。

链接：

大意：

给定一个整数数组nums，一个整数k，一个整数n。要求判断数组nums中是否存在不同的两个索引下标i和j，使得 |i - j| <= k 并且 |nums[i] - nums[j]| <= t。例子：

思路：

暂时没想到好方法，只能暴力法先解决了。

代码：

class Solution {    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {        if (k < 0 || t < 0)            return false;        for (int i = 0; i < nums.length; i++) {            for (int j = 1; j <= k && i + j < nums.length; j++) {                // 将int转换为long 为了解决Integer.MAX_VALUE + 1产生的int越界问题                if (Math.abs((long)nums[i] - (long)nums[i + j]) <= t)                    return true;            }        }        return false;    }}

结果：

结论：

效率很低，有待改进。 

改进一：（基于窗口思想）

参考：

public class Solution {    // 窗口思想    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {        if (nums == null || nums.length == 0 || k <= 0) {            return false;        }        final TreeSet
   
     values = new TreeSet<>(); // 存储Long 解决int越界        for (int ind = 0; ind < nums.length; ind++) {            final Long floor = values.floor((long)nums[ind] + t); // 得到小于等于nums[ind] + t的最大的数            final Long ceil = values.ceiling((long)nums[ind] - t); // 得到大于等于nums[ind] - t的最小的数            if ((floor != null && floor >= nums[ind])                    || (ceil != null && ceil <= nums[ind])) {                return true;            }            values.add((long)nums[ind]);            if (ind >= k) {                values.remove(new Long(nums[ind - k]));            }        }        return false;    }}
   

改进二：（不使用TreeSet维护有序窗口（TreeSet调整自身顺序也是需要时间，况且使用floor和ceiling函数的时间复杂度为O(log n)），而是使用HashSet维护窗口）

class Solution {    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {        if (nums == null || nums.length == 0) return false;        if (k<1 || t<0) return false;        HashSet
   
     set = new HashSet<>();        for (int i = 0; i < nums.length; i++){            if (t == 0){                if (set.contains(nums[i]))                    return true;            }else{                for (int ii : set){                    if (Math.abs((long)((long)ii-(long)nums[i])) <= t)                        return true;                }            }            set.add(nums[i]);            if (set.size() == k+1)                set.remove(nums[i-k]); // remove Object        }        return false;    }}
   

转载地址：http://saesi.baihongyu.com/