题目来源
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.
说实话，没啥想法。
然后看了下答案，用的桶排序的方法，就是每个桶的大小四t，然后假如k个数中有两个数在一个桶内，那么返回true，假如在隔壁桶但是距离小于t，也返回true，然后不断的增删遍历。
要注意几种边界情况，比如t是INT_MAX之类的，t是0啊之类的。
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
auto n = nums.size();
if (n < 2 || k < 1 || t < 0)
return false;
unordered_map<long, long> map;
for (int i=0; i<n; i++) {
long bn = (long(nums[i]) - INT_MIN) / (long(t) + 1);
if (map.find(bn) != map.end() || (map.find(bn-1) != map.end() && nums[i] - map[bn-1] <= t) || (map.find(bn+1) != map.end() && map[bn+1] - nums[i] <= t))
return true;
map[bn] = nums[i];
if (map.size() > k) {
cout << map.size() << endl;
long rbn = (long(nums[i-k]) - INT_MIN) / (long(t) + 1);
map.erase(rbn);
}
}
return false;
}
};
