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

题目描述如下：

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

一入眼看到了BST就想着要自己建立数据结构，虽然知道LeetCode对于必须的数据结构是会主动提供的，按着数组来时间复杂度肯定是n平方，又想不到别的办法，硬着头皮自己写了BST等等，还好最后给弄出来了；

思路很简单：首先由数组建立BST，然后对于树中的每个元素都有根节点开始查找，其实相当于实现了BST的put和get，不过稍稍变了形，代码如下：

public class Solution {    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {        if(nums.length == 0)            return false;        BST tree = new BST(k, t);        for(int i = 0; i < nums.length; i++)            tree.put(i, nums[i]);        return tree.searchFromRoot(tree.root);    }        class BST{        Node root;        int k, t;        public BST(int k, int t){            root = null;             this.k = k;            this.t = t;        }                public boolean searchFromRoot(Node temp){            // return searchChildTree(root);            if(searchChildTree(root, temp.value, temp.key))                return true;            if(temp.left != null){                if(searchFromRoot(temp.left))                	return true;            }                        if(temp.right != null){                if(searchFromRoot(temp.right))                    return true;            }            return false;        }                public boolean searchChildTree(Node n, long val, long key){           Node right = n.right;           Node left = n.left;           if(n.key != key && Math.abs(n.value - val) <= t && Math.abs(n.key - key) <= k)        	   return true;           if(right != null){               if(Math.abs(right.value - val) <= t){                   if(right.key != key && Math.abs(right.key - key) <= k)                        return true;                    if(right.right != null){                        return searchChildTree(right.right, val, key);                    }               }//end if Math.abs(right.value - val) <= t               if(right.left != null){                    return searchChildTree(right.left, val, key);                }           }//end if right != null                      if(left != null){               if(Math.abs(left.value - val) <= t){                   if(left.key != key && Math.abs(left.key - key) <= k)    return true;                   if(left.left != null)                            return searchChildTree(left.left, val, key);               }               if(left.right != null)                        return searchChildTree(left.right, val, key);           }           return false;        }                public void put(int key, int value){            root = put(root, key, value);        }                public Node put(Node root, int key, int val){            Node newNode = new Node(key, val);            if(root == null)                return newNode;            if(val <= root.value)                root.left = put(root.left, key, val);            else                root.right = put(root.right, key, val);            return root;        }                private class Node{            int key;            int value;            Node left, right;                    public Node(int key, int value){                this.key = key;                this.value = value;                left = null;                right = null;            }        }    }}

AC之后又上网看了别人的代码，果然too young too simple，看了别人吊炸天的代码瞬间觉得自己弱爆了。。。TreeSet不是没看到过，就是不会用，下面是从大神那copy的，希望不会造成侵权神马的。。

import java.util.SortedSet;public class Solution {    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {        //input check        if(k<1 || t<0 || nums==null || nums.length<2) return false;                SortedSet
   
     set = new TreeSet
    
     ();                for(int j=0; j
     
       subSet =  set.subSet((long)nums[j]-t, (long)nums[j]+t+1);            if(!subSet.isEmpty()) return true;                        if(j>=k) {                set.remove((long)nums[j-k]);            }            set.add((long)nums[j]);        }        return false;    }}
     
    
   

加油加油！！！

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