STL训练清单

训练清单传送门

• 我的主要博客

multimap的训练集

参考文章：multimap::equal_range
multimap::count

• 题目传送门：219. 存在重复元素 II

multimap的好题目

• 注意：multimap其中没有_，不像unordered_map

方法1

• map和multimap一起用

• 『『这种累计方式的Hash我前2天也写过，还是学习自别人那里的』』』

• 难点在于：mulimap很少用，其中的equal_range()成员函数虽然在map和multimap中

• 都有用到，但是很少用

• 此外，mulimap没有[]

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int,int> mp;
        multimap<int,int> HelpCount;
        int Len=nums.size();
        for(int i=0; i<Len; ++i)
        {
            int CurNum=nums[i];
            //如果前面有等于的
            if( mp.count( CurNum ) )
            {
                auto Begin2End=HelpCount.equal_range( CurNum );
                            //下面的这种写法，以前很少写！！
                            //参考自：http://www.cplusplus.com/reference/map/multimap/equal_range/
                for( auto it=Begin2End.first; it!=Begin2End.second; ++it)
                {
                    //cout<< (*it).second <<endl;
                    if( i-(*it).second <=k )
                    {
                        return true;
                    }
                }

            }
            mp[ CurNum ]++;
            //注意：multimap是没有[]的
            HelpCount.insert( make_pair( CurNum, i) );
        }

        return false;
    }
};

方法2

• map和滑动窗口一起用
• 就是将<=k和multimap转换为滑动窗口来写