刷题主页
在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。 如果存在则返回 true，不存在返回 false。 示例 1: 输入: nums = [1,2,3,1], k = 3, t = 0 输出: true 示例 2: 输入: nums = [1,0,1,1], k = 1, t = 2 输出: true 示例 3: 输入: nums = [1,5,9,1,5,9], k = 2, t = 3 输出: false
读题时先发现关键点：下标的差的绝对值小于等于k，说明是在一个区间内寻找满足条件的数，见到对数组下标有限制条件时就该想到滑动窗口，接下来查找满足条件的数，nums[i]和nums[j]的绝对值小于t，说明对于数nums[i]，应该找到nums[j]使得，nums[i]-t<=nums[j]<=nums[i]+t，暴力搜索的话会超时，因此使用二分法搜索，使用辅助数据结构set,再进行二分法即可得到结果。这里注意搜索满足某条件的数时通常暴力都是不行的，这时需要借助辅助数据结构，常用的是set，hash表。
class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { int len=nums.size(); set<long>st; for(int i=0;i<len;++i){ auto it=st.lower_bound((long)nums[i]-t); if(it!=st.end() && *it<=(long)nums[i]+t)return true; st.insert(nums[i]); if(st.size()>k)st.erase(nums[i-k]); } return false; } };