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.
思路
基本思路是，假设当前运行到nums[i]的位置，则需要往前看k个数，并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题（问题就转变为：找到第一个>=nums[i]-t的数，判断他是否<=nums[i]+t）。整个算法的时间复杂度是O(N * logk)，N为数组长度。
下面代码中用set实现，set是用红黑树实现的。
代码
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if(nums.empty() || k<1 || t<0)
return false;
k++;
set<int> kNumSet;
for (int i=0; i<nums.size(); i++){
if(i >= k){
int oldVal = nums[i-k];
kNumSet.erase(oldVal);
}
auto l_bound = kNumSet.lower_bound(nums[i] - t);
if(l_bound != kNumSet.end()){
if(*l_bound - t <= nums[i])
return true;
}
kNumSet.insert(nums[i]);
}
return false;
}
};