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.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0 Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false
给定一个数组，问是否存在两个相距k之内的差的绝对值在t之内的数。
这个题有点难度，是LeetCode Contains Duplicate II的升级版。
首先，要求距离在k之内，所以想到维护一个长度为k的滑动窗口，在这个滑动窗口内判断是否有差的绝对值在t之内的两个数。
具体参考讨论区。用一个set来保存长度为k的滑动窗口window，每次往前滑动一格，如果窗口大于k了，则删除窗口左边的元素。对于即将进入窗口的数nums[i]，我们需要判断窗口内是否存在一个x，使得$|x-nums[i]|\leq t$，展开就是$nums[i]-t\leq x\leq t+nums[i]$。
由于set内部是有序的树结构，所以可以用set.lower_bound直接判断大于等于$nums[i]-t$的数x是否在window中。如果在的话，我们再判断是否满足$x\leq t+nums[i]$，这个式子等价于$x-nums[i]\leq t$，为什么要这么写呢，因为nums[i]有可能是INT_MAX或者INT_MIN，为了防止溢出，需要把相关的操作数转换为long long。
完整代码如下：
typedef long long ll;
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
set<ll> window;
for (int i = 0; i < nums.size(); ++i) {
if (i > k)
window.erase(nums[i – k – 1]); // 删除窗口左边的元素
auto it = window.lower_bound(ll(nums[i]) – t); // x>=nums[i]-t
if (it != window.end() && *it – nums[i] <= t)
return true; // x<=nums[i]+t
window.insert(nums[i]);
}
return false;
}
};本代码提交AC，用时19MS。