解题思路:
使用set集合来实现滑动窗口k,对窗口内的数进行比较,得到结果。
使用两个指针i、j,来确定窗口位置,i走在前面,j在后面。因为数组内这两个数的差值绝对值限制为:| x - nums[i] | < t,所以,有 nums[i] - t < x < nums[i] + t,所以,我们要在set s中找到nums[i] - t所在的位置,如果找到了,说明窗口内有满足这左侧不等式的数x,再判断右侧不等式x < nums[i] + t是否满足,如果均满足,即找到,返回true。如果不满足其一,就将窗口向右平移一位。
主要使用了lower_bound函数。
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long long> s;
for(int i = 0, j = 0; i < nums.size(); i++){
if(i - j > k){
s.erase(nums[j++]);
}
auto it = s.lower_bound((long long)nums[i] - t);
if(it != s.end() && abs(*it - nums[i]) <= t) return true;
s.insert(nums[i]);
}
return false;
}
};