LeetCode 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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
注意题目中一旦出现，当两者距离at most k等constraint时，都可以考虑使用sliding window的方法，每次仅保留window size=k的元素，判断完后再移动并更新window。
思路一：naive thinking
考虑排序，但排序时也得带上index，即需要记录排序前各个元素原先的下标。排序后，check数组中是否存在符合at most t & at most k的元素。
思路二：基于sliding window
顺序扫描数组，每次仅保存size=k的滑动窗口，并用TreeSet或bucket存储窗口中现有的元素，加入新元素后判断是否与集合中元素满足difference<=t的条件。注意窗口的更新，如何维护treeset或bucket（加入新元素的同时，删除最早加入的元素）。
这里要注意为什么需要使用treeset与bucket，而不是queue？原因是treeset和bucket具有根据input value快速查找的能力，若新加入的元素为nums[i]，
则treeset可以通过floor与ceiling在O(log k)的时间复杂度下查找最相近的元素。
Long floor = set.floor((long) nums[i]);
Long ceiling = set.ceiling((long) nums[i]);
bucket可以在O(1)时间复杂度下查找，原因是将出入分成了大小为t+1的桶，这里类似于hashmap，可以根据输入大小nums[i]直接反查在哪个桶中。
long remappedNum = (long) nums[i] - Integer.MIN_VALUE;
long bucket = remappedNum / ((long) t + 1);
基于treeset的代码如下
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// Deal with corner cases
if (k <= 0 || nums.length < 2) {
return false;
}
TreeSet<Long> set = new TreeSet<>();
// Scan using sliding window
int i = 0;
while (i < nums.length) {
Long floor = set.floor((long) nums[i]);
Long ceiling = set.ceiling((long) nums[i]);
if (floor != null && nums[i] - floor <= t ||
ceiling != null && ceiling - nums[i] <= t)
return true;
if (i >= k) {
set.remove((long) nums[i-k]);
}
set.add((long) nums[i++]);
}
return false;
}
}
参考：
https://discuss.leetcode.com/topic/15191/java-o-n-lg-k-solution/13
