# Array - 220. Contains Duplicate III

220、 Contains Duplicate III

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.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

1. 使用暴力求解的时间复杂度是O(N*K)，空间复杂度为O(1)。
2. 使用BST来记录位置的和值可以把时间复杂度优化到O(N*logk)，但是额外使用了map所以空间复杂度为O(k)。
3. 使用bucket的思想和BST来查找最接近的值与当前值的差值，时间复杂度可以为O(n)，空间的复杂度与bucket的size有关，最差就是对每一个数字都建立一个bucket。

java：

``````class Solution {

/*public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

if (nums == null || nums.length == 0 || k <= 0 || t <0) return false;

TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
Long ceil = set.ceiling((long)nums[i] - t);
Long floor = set.floor((long)nums[i] + t);

if ((floor != null && floor >= nums[i]) || (ceil != null && ceil <= nums[i])) {
return true;
}

if (i >= k) {
set.remove((long)nums[i-k]);
}
}

return false;
}*/

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0) return false;
Map<Long, Long> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
long bucket = remappedNum / ((long) t + 1);
if (map.containsKey(bucket)
|| (map.containsKey(bucket - 1) && remappedNum - map.get(bucket - 1) <= t)
|| (map.containsKey(bucket + 1) && map.get(bucket + 1) - remappedNum <= t))
return true;
if (map.entrySet().size() >= k) {
long lastBucket = ((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1);
map.remove(lastBucket);
}
map.put(bucket, remappedNum);
}
return false;
}
}
``````

Nothing just happens, it's all part of a plan.