这一题比较类似https://cloud.tencent.com/developer/article/2028497
需要使得区间中的两个元素满足相差小于t,可推导为 v-t <= v <= v+t ,
可以考虑使用C++的 lower_bound( v-t ) 寻找大于 v-t 的最小的元素 ,进而可以查出查找表中是否有满足条件的值。代码如下,这里需要特别注意整型溢出的问题:
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long> counter;
for(int i = 0;i < nums.size() ;i++){
if (counter.lower_bound((long)nums[i]-(long)t) != counter.end() && *counter.lower_bound((long)nums[i]-(long)t) <= (long)nums[i]+(long)t )
return true;
else{
counter.insert(nums[i]);
}
if(counter.size() >= k+1){
counter.erase((long)nums[i-k]);
}
}
return false;
}
};