220. Contains Duplicate III

本文主要是介绍220. Contains Duplicate III，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：
因为固定了是在 [i-k，i+k]的区间内寻找 在区间[nums[i]-t，nums[i]+t]的元素，所以可以考虑用滑动窗口，但是这里并不用双指针来操作，不然和暴力没区别了。
我们要找到一个数据结构，能够自动排序，因为排序我们就能直接找到K窗口里面的最小值和最大值，优化找到[nums[i]-t，nums[i]+t]的方法，还需要能高效的查找和删除元素，我们用set来维护k大小的窗口，当窗口存放K+1个元素后就会删掉最先加入的元素，然后变为只有K个元素的窗口开始下一次循环。
这里用set，因为是有序的序列才可以用lower_bound来寻找第一个大于等于nums[i]-t的元素，然后再判断是否小于nums[i]+t，如果小于那么就找到了返回true。如果不满足还是加入进set这个窗口里，因为不过怎么样我们滑动过去都会加入它。
同时题目给的数据会超int，所以要用INT_MIN和MAX来限制，

代码：

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n=nums.size();
        set<int> rec;
        for(int i=0;i<n;++i){
            auto ite =rec.lower_bound(max(nums[i],INT_MIN+t)-t);  //INT_MIN用来限制小于int范围的数据，找到第一个大于等于nums[i]-t的元素
            if(ite!=rec.end()&&*ite<=min(nums[i],INT_MAX-t)+t){   //INR_MAX用来限制大于int范围的数据，判断是否小于nums[i]+t
                return true;
            }
            rec.insert(nums[i]);
            if(i>=k){  //移动窗口，并维护
                rec.erase(nums[i-k]);
            }
        }
        return false;
    }
};

另一种方法，我们将每t范围的数放入一个桶里，如t=3，那么将0123|4567|这样将最大和最小值值差为3的数放如一个桶里，那么我们每次只要用一个数除以k+1即可得到他应该在的桶的编号，如果桶存在，那么就存在满足要求的数，返回true，否则就检查它旁边的桶，查看里面是否有数字满足 abs(nums[i]-mp[idx])<=t，如果有，那么也返回true。如果都没有，那么就创建这个桶。所以，每个桶只会有一个数，如果有两个数，那么自然就返回true了。那么当i>=k的时候，也要将这个桶去除，相当于去除这个数。
先上代码，这里有个问题：

#define LL long long
class Solution {
private:
    LL size;
public:
    LL get_idx(LL num){
        return num<0? (num+1)/size-1:num/size;
    }
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map<LL,LL> mp;
        int n=nums.size();
        size = t+1L;
        for(int i=0;i<n;++i){
            LL num=nums[i]*1L;
            LL idx=get_idx(num);
            if(mp.find(idx)!=mp.end()) return true;
            LL l=idx-1,r=idx+1;
            if(mp.find(l)!=mp.end() && abs(num-mp[l])<=t) return true;
            if(mp.find(r)!=mp.end() && abs(num-mp[r])<=t) return true;
            mp.insert({idx,num});
            if(i>=k) mp.erase(get_idx(nums[i-k]*1L));
        }
        return false;
    }
};

这里的get_idx函数，是用来处理负数和整数桶的标号的。
首先size=t+1，则桶里装的0123，3-0=3；4567，7-4=3，差才能保证不小于t。详情可看
对于负数有 （num+1）/size +1，的原因是在处理正数的时候已经把0算如正数了，那么对于负数只能右移一位，创建出一个0得到（num+1）/size 才能与正数的对称，分割方法和正数一样。这之后在左移回去即可。

这篇关于220. Contains Duplicate III的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！