//时间：O(n)

//空间：O(k)

class Solution {

public:

    bool containsNearbyDuplicate(vector<int>& nums, int k) {

        unordered_set<int> record;   //查找表

        for(int i=; i<nums.size();i++)

        {

            if(record.find(nums[i])!= record.end() )

                return true;

            record.insert(nums[i]);

            //保持record中最多有k个元素，当右边有一个新的元素加入时，窗口才会变成k+1

            if(record.size()==k+)

                record.erase(nums[i-k]);

        }

        return false;

    }

};

class Solution {

public:

    bool containsDuplicate(vector<int>& nums) {

        unordered_map<int, int> mp;

        for(int a: nums){

            if(mp.find(a)==mp.end()){

                //没找到重复元素

                mp[a] +=;

            }

            else

                return true;

        }

        return false;

    }

};

class Solution {

public:

    bool containsDuplicate(vector<int>& nums) {

        unordered_set<int> record;

        for(int i=;i<nums.size();i++){

            if(record.find(nums[i])!=record.end())

                return true;

            record.insert(nums[i]);

        }

        return false;

    }

};

class Solution {

public:

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

        //long long 64位整型

        set<long long > record;  //因为调用lower_bound 需要有顺序性，所以使用set

        for(int i=;i<nums.size();i++){

            //查找大于或等于nums[i]-t的第一个元素的位置

            if(record.lower_bound( (long long)nums[i]-(long long)t) != record.end() &&

              *record.lower_bound( (long long)nums[i]-(long long)t)<= (long long)nums[i]+(long long)t)

                return true;

            record.insert(nums[i]);

            if(record.size() == k+)

                record.erase(nums[i-k]);

        } 

        return false;

    }

};