set实现了红黑树的平衡二叉树，其搜索速度远远大于其他的线性结构。在最开始使用vector实现，最后一个用例一直提示超时，统计了一下时间有5s+（debug模式），之后参考评论使用set。结果accept了。统计了时间是0.5s+
class Solution {public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { int size = nums.size(); int setSize = k + 1 <= size ? k + 1 : size; if (setSize <= 1) { return false; } // 此处不用考虑重复元素，因为如果两个相同的元素在同一个k的区域范围内 // 就是说这两个元素的差是0，一定是符合的。 set<double> s; for (int i=1; i < size; i++) { double low = (double)nums[i] - t; double up = (double)nums[i] + t; if (i <= k) { s.insert(nums[i - 1]); } else { s.erase(nums[i - k - 1]); s.insert(nums[i - 1]); } set<double>::iterator ptr = s.lower_bound(low); if (ptr != s.end() && *ptr <= up) { return true; } } return false; }};新闻热点
疑难解答
