题目描述
题解
对于位置 \(i\) ，满足规则2的合法下标范围是 [i-indexDiff,i+indexDiff] ,因此设置一个滑动窗口，窗口大小为indexDiff，从数组位置0开始进行滑动。这样，当遍历到某个位置 \(x\) 时，窗口包含 \(x\) 前边最多 indexDiff 个元素。此时我们可以检查窗口中是否有某个数据落在了[x-valueDiff, x+valueDiff] 之间。
如果使用队列维护滑动窗口内的元素，由于元素是无序的，我们只能对于每个元素都遍历一次队列来检查是否有元素符合条件。如果数组的长度为 \(n\)，则使用队列的时间复杂度为 \(O(n·indexDiff)\)会超出时间限制。
因此我们希望能够找到一个数据结构维护滑动窗口内的元素，该数据结构需要满足以下操作：
1.支持添加和删除指定元素的操作，否则我们无法维护滑动窗口；
2.内部元素有序，支持二分查找的操作，这样我们可以快速判断滑动窗口中是否存在元素满足条件，具体而言，对于元素 \(x\)，我们希望判断滑动窗口中是否存在某个数 \(y\) 落在[x-valueDiff, x+valueDiff] 之间，我们只需查找区间中大于等于 x-valueDiff 的最小元素是否小于等于 x+valueDiff
对于上述要求，C++中的set可以满足。
实现方面，我们在有序集合中查找大于等于 x−valueDIff的最小的元素 y，如果 y 存在，且 y≤x+valueDiff，我们就找到了一对符合条件的元素，则可返回true。反之，我们将 x 插入到有序集合中，如果有序集合中元素数量超过了 indexDiff，我们将有序集合中最早被插入的元素删除即可。
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff)
{
int n = nums.size();
set<long long> rec;
for(int i = 0; i < n; i++)
{
set<long long> :: iterator it = rec.lower_bound(nums[i] - valueDiff);
if(it != rec.end() && *it <= (nums[i] + valueDiff))
return true;
//i从0开始
rec.insert(nums[i]);
if(i >= indexDiff)
rec.erase(nums[i - indexDiff]);
}
return false;
}
};
时间复杂度 \(O(nlog(min(n, indexDiff)))\) ,其中 \(n\) 是给定数组的长度。每个元素至多被插入有序集合和从有序集合中删除一次，每次操作时间复杂度均为 \(O(log(min(n,k))\)。
空间复杂度 \(O(min(n, indexDiff))\)
滑动窗口适用于求解连续k个数中搜寻满足某个条件的数的问题
题解2
然而，该题还有另一种巧妙的方法。可以利用桶排序的思想解决本题，我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。
对于元素 \(x\)，满足条件的范围为 [x-valueDiff,x+valueDiff]. 为此我们采用分桶方法，将每个桶的大小设置为 valueDiff+1。如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 valueDiff。如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。
具体地，我们遍历该序列，假设当前遍历到元素 \(x\)，那么我们首先检查 \(x\) 所属于的桶是否已经存在元素，如果存在，那么我们就找到了一对符合条件的元素，否则我们继续检查两个相邻的桶内是否存在符合条件的元素。
从实现方面，由于设置了桶大小为valueDiff+1，因此需要给int范围内实数进行标号，如0-valueDiff范围内的实数标为0，即放在第一个桶中。
打个比方：
这里假设t=10，则根据我们的求解思路，必须要使每个桶的容纳范围为11，即桶的容量要设置为11。对于大于等于0的数，显然用该数除以11即可得到这个数字正确的桶编号，由于C++中正小数负小数进行整除时，都是向0取整的，所以对于负数，应当设计出不同于正数的编号方法，研究得到如下编号方法：
当x>=0时， id = x/(t+1); 当x<0时， id = (x+1)/(t+1)-1.
这样的分组效果如下： ... -2号桶：-12 ~ -22； -1号桶：-1 ~ -11； 0号桶： 0~10； 1号桶： 11 ~ 20 ...
class Solution {
public:
int getID(int x, long w) {
return x < 0 ? (x + 1) / w - 1 : x / w;
}
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
unordered_map<int, int> mp;
int n = nums.size();
for (int i = 0; i < n; i++) {
long x = nums[i];
int id = getID(x, t + 1);
if (mp.count(id)) {
return true;
}
if (mp.count(id - 1) && abs(x - mp[id - 1]) <= t) {
return true;
}
if (mp.count(id + 1) && abs(x - mp[id + 1]) <= t) {
return true;
}
mp[id] = x;
if (i >= k) {
mp.erase(getID(nums[i - k], t + 1));
}
}
return false;
}
};