219. Contains Duplicate II

在这里用了multimap bug出在前置++和->的优先级顺序，也就是正文注释处，一直没加小括号

时间复杂度为O(NlogN)；

class Solution {

public:

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

// map<int, int> imap; 如果有三个或更多相同的数 此后只能跟仅插入的第一个数的下标比较

// for(int i = 0; i != nums.size(); ++i) 所以放弃这个思路 改用UNorder map

// if(imap.find(nums[i] == imap.end()))

// imap.insert(nums[i], i);

// else

multimap<int, int> imap;

for(int i = 0; i != nums.size(); ++i)

imap.insert({nums[i], i});

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

auto icount = imap.count(nums[i]);

auto iter = imap.find(nums[i]);

while(icount - 1) {

if(iter->second + k >= (++iter)->second)    //bug

return true;

--icount;

}

}

return false;

}

};

答案中用set的方法 更快内存更小 时间O（N）

class Solution {

public:

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

{

unordered_set<int> s;

if (k <= 0) return false;

if (k >= nums.size()) k = nums.size() - 1;

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

{

if (i > k) s.erase(nums[i - k - 1]);

if (s.find(nums[i]) != s.end()) return true;

s.insert(nums[i]);

}

return false;

}

};