问题传送门
此问题划分为两个问题： 1、定义一个大小为k的窗口，其最右端元素与左侧任意元素组合是否能满足diff < t的要求。 2、当上一个窗口不存在时，我们需要滑动窗口，此时窗口中的元素发生变化，第一个元素移除，窗口的next元素进入。我们如何利用原有窗口的数据来高效执行，即减少重复计算。
此代码利用set保存有序顺序的特性，来保证每次增加和删除时窗口内部的数据有序，且增加和删除时时间复杂度为logk（具体参考红黑树）。通过此例我们可以知道当我们想要维护一个时常进行增加删除的有序集合时，可以通过set来实现。 在有序数据集中查找符合条件的diff，其采用两步走方式。 |x - windows[last]| <= t ===>-t <= x - windows[last] <= t ===> -t + windows[last]<= x <= t + windows[last] 其中windows[last]表示窗口中最右侧元素，x表示符合条件的目标元素 我们先查找满足 -t + windows[last] <= x 的最小值 mm， 如果mm <= t + windows[last]便表示存在一个合法值。 在set中进行lower_bound查找相当于二叉查找，时间复杂度log k。
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<int> window; // set is ordered automatically for (int i = 0; i < nums.size(); i++) { if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k // |x - nums[i]| <= t ==> -t <= x - nums[i] <= t; auto pos = window.lower_bound(nums[i] - t); // x-nums[i] >= -t ==> x >= nums[i]-t // x - nums[i] <= t ==> |x - nums[i]| <= t if (pos != window.end() && *pos - nums[i] <= t) return true; window.insert(nums[i]); } return false; }下面的答案采用桶分类的方式进行求解，其时间复杂度更低 原始答案解析 此方法在处理时使用bucket进行分类，bucket按照 t + 1为间隔进行分割。 1、同一个bucket，其值必定只差小于 t 2、相邻bucket，可能存在，此时需要进行额外判断 3、bucket相距大于1，则其间隔大于 t + 1。
class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { int n = nums.size(); if(n == 0 || k < 0 || t < 0) return false; unordered_map<int,int> buckets; for(int i=0; i<n; ++i) { int bucket = nums[i] / ((long)t + 1); // For negative numbers, we need to decrement bucket by 1 // to ensure floor division. // For example, -1/2 = 0 but -1 should be put in Bucket[-1]. // Therefore, decrement by 1. if(nums[i] < 0) --bucket; if(buckets.find(bucket) != buckets.end()) return true; else { buckets[bucket] = nums[i]; if(buckets.find(bucket-1) != buckets.end() && (long) nums[i] - buckets[bucket-1] <= t) return true; if(buckets.find(bucket+1) != buckets.end() && (long) buckets[bucket+1] - nums[i] <= t) return true; if(buckets.size() > k) { int key_to_remove = nums[i-k] / ((long)t + 1); if(nums[i-k] < 0) --key_to_remove; buckets.erase(key_to_remove); } } } return false; } };