220. Contains Duplicate III - jiejackyzhang/leetcode-note GitHub Wiki
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.
解题思路为使用TreeSet，这是一种红黑树结构。
顺序扫描数组，TreeSet中存储当前元素的前k个元素，查找有无符合条件的数。 在TreeSet中查找O(logk)，因此总的时间复杂度为O(nlogk)。
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(nums == null || nums.length < 2 || k == 0) return false;
TreeSet<Long> values = new TreeSet<>();
for(int i = 0; i < nums.length; i++) {
Long floor = values.floor((long)(nums[i] + t));
Long ceil = values.ceiling((long)(nums[i] - t));
if((floor != null && floor >= nums[i]) || (ceil != null && ceil <= nums[i])) return true;
values.add((long) nums[i]);
if(i >= k) {
values.remove((long) nums[i-k]);
}
}
return false;
}
}