1. 219

contains-duplicate-ii

2. 算法

• set:O(nlgn)

加上一个窗口k

• map:O(nlgn)

3.代码

* 加窗算法

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
         // set only record k(or less that k)  numbers of before nums[i]
        set<int> st;
        for(int i=0;i<nums.size();++i){
            if(st.find(nums[i])!=st.end())
                return true;
            if(st.size()<k){
                    st.insert(nums[i]);
                }
            else{
                //insert first,or wrong when k=0

                st.insert(nums[i]);
                st.erase(nums[i-k]);
            }
        }

        return  false;

     }

};

3.2

* 哈希

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        //map(number,index)
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();++i){
            if(mp.find(nums[i])!=mp.end() && mp[nums[i]]>=i-k)
                return true;
        mp[nums[i]]=i;
    }
    return false;
    }
};