### 题目

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

### 暴力窗口内遍历，复杂度 $O(n*t)$

#### 代码

public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length < 2) { return false; }
for (int slow = 0, fast = 1; fast < nums.length; fast++) {
if (fast > k) { slow++; }
int newNum = nums[fast];
for (int cur = slow; cur < fast; cur++) {
long diff = Math.abs((long)nums[cur] - (long)newNum); // use long to avoid overflow
if (diff <= t) { return true; }
}
}
return false;
}
}


### HashMap Bucket，复杂度 $O(n)$

5为除数，每个数字存入HashMap之前，都先除以5

HashMap中的每个键值 key 都对应了 5 个数字 （叫一个bucket）：

lo                 target                hi
|                   |                   |
... ...  |  130,131,132,133,134  |  135,136,137,138,139  |  140,141,142,143,144  |  ... ...
key = 25           key = 26                key = 27                key = 28            key = 29

|                        |                      |
current bucket -1           current bucket      current bucket + 1

[lo,hi]中的所有数字都一定在[bucket-1,bucket,bucket+1]左中右3个bucket中。


#### 几个corner case

##### 0的问题

bucket映射的效果，相当于以0为中心，向中间压缩数轴。所有bucket = 0中的数字会多出一倍。


... ... |  -10,-8,-7,-6,-5  |  -4,-3,-2,-1,0,1,2,3,4  |  5,6,7,8,9  |  ... ...
key = -1                key = 0              key = 1


#### 代码

public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length < 2) { return false; }
if (t < 0) { return false; }
Map<Long,Long> buckets = new HashMap<>();
Long[] bucketMemo = new Long[nums.length];
for (int i = 0, j = 0; j < nums.length; j++) {
Long numL = (long)nums[j] - Integer.MIN_VALUE;
Long bucket = numL / ((long)t + 1);
bucketMemo[j] = bucket;
if (j > k) { buckets.remove(bucketMemo[i++]); }
// check: bucket-1, this bucket and bucket+1
if (buckets.get(bucket) != null) { return true; } // this bucket
Long left = buckets.get(bucket-1);
if (left != null && (numL - left) <= t) { return true; } // bucket-1
Long right = buckets.get(bucket+1);
if (right != null && (right - numL) <= t) { return true; } // bucket+1
buckets.put(bucket,numL);
}
return false;
}
}


### 利用二叉树做范围检查

#### 代码

public class Solution {
private static class TreeNode {
private long val;
private TreeNode left;
private TreeNode right;
private TreeNode(long n) { val = n; }
}
private static class BinarySearchTreeWithDummy {

private TreeNode dummy = new TreeNode(0); // sentinel

/** Insert new element into the tree
*  Return true if new value is added
*  Return false if this value is already exist
*/
TreeNode pre = dummy, cur = dummy.right; // head is always the right child of dummy
boolean fromLeft = false;
while (cur != null) {
long val = cur.val;
if (val > n) { // go left
pre = cur; cur = cur.left; fromLeft = true;
} else if (val < n) { // go right
pre = cur; cur = cur.right;
} else { // value already exist
return false;
}
}
TreeNode newNode = new TreeNode(n);
if (fromLeft) {
pre.left = newNode;
} else {
pre.right = newNode;
}
return true;
}
/**
* Return true if the target is removed
* Return false if target doesn't exist
*/
private boolean remove(long n) {
TreeNode pre = dummy, cur = dummy.right;
boolean fromLeft = false;
while (cur != null) {
if (cur.val > n) { // go left
pre = cur; cur = cur.left; fromLeft = true;
} else if (cur.val < n) { // go right
pre = cur; cur = cur.right;
} else { // find target
if (cur.left != null) {
cur = cur.left;
while (cur.right != null) { cur = cur.right; }
} else {
}
if (fromLeft) {
} else {
}
return true;
}
}
return false;
}
/**
* Return least element greater than the input n
* Return null if there is no element greater than n
*/
private Long ceiling(long n) {
TreeNode lastGreater = null;
TreeNode cur = dummy.right;
while (cur != null) {
if (cur.val > n) { // go left
lastGreater = cur; cur = cur.left; // use lastGreater to mark the last element greater than target , thus we don't need to rollback when we reach the leaf of the tree.
} else if (cur.val < n) {
cur = cur.right;
} else { // find target
return new Long(cur.val);
}
}
return (lastGreater == null)? null : new Long(lastGreater.val);
}
}
/**
* Solution based on Binary Search Tree
* Use my BinarySearchTreeWithDummy
*/
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length < 2) { return false; }
if (t < 0) { return false; }
BinarySearchTreeWithDummy tree = new BinarySearchTreeWithDummy();
for (int slow = 0, fast = 0; fast < nums.length; fast++) {
if (fast > k) { tree.remove((long)nums[slow++]); }
long floor = (long)nums[fast] - t;
long ceil = (long)nums[fast] + t;
Long firstGreaterThanFloor = tree.ceiling(floor);
if (firstGreaterThanFloor != null && firstGreaterThanFloor <= ceil) { return true; }
}
return false;
}
}


### 用库自带容器TreeSet实现

#### 代码

/**
* Another solution based on Binary Search Tree
* But use in-build TreeSet Container
*/
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums.length < 2) { return false; }
if (t < 0) { return false; }
TreeSet<Long> tree = new TreeSet<>();
for (int slow = 0, fast = 0; fast < nums.length; fast++) {
if (fast > k) { tree.remove((long)nums[slow++]); }
// System.out.println("Slow=" + slow + ", Fast=" + fast + ", Tree= " + tree);
long floor = (long)nums[fast] - t;
long ceil = (long)nums[fast] + t;
Long firstGreaterThanFloor = tree.ceiling(floor);
if (firstGreaterThanFloor != null && firstGreaterThanFloor <= ceil) { return true; }
}
return false;
}
}


#### 结果

TreeSetceiling()函数，最终调用的是TreeMap中的getCeilingEntry()函数。但这个函数写得不好，它没有在遍历的过程中在内存中记录下前一个大于目标值的元素。而是采用遍历到底层叶节点之后，回滚的方式。效率所以不如我的高。

final Entry<K,V> getCeilingEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) {
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) {
if (p.right != null) {
p = p.right;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.right) { // 跑到右子树以后需要向上回滚
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
`