[leetcode] Contains Duplicate II

 1 class Solution
 2 {
 3 public:
 4   bool containsNearbyDuplicate(vector<int> &nums, int k)
 5   {
 6     set<int> S;
 7     int start = 0, end  = 0;
 8 
 9     for(int i=0; i<nums.size(); i++)
10     {
11       if(S.find(nums[i]) != S.end())
12         return true;
13       else
14       {
15         S.insert(nums[i]);
16         end++;
17       }
18 
19       if(end-start > k)
20       {
21         S.erase(nums[start]);
22         start++;
23       }
24     }
25 
26     return false;
27   }
28 };

 1 class Solution
 2 {
 3 public:
 4   bool containsNearbyDuplicate(vector<int> &nums, int k)
 5   {
 6     map<int, int> M;
 7 
 8     for(int i=0; i<nums.size(); i++)
 9     {
10       if(M.find(nums[i]) != M.end() && i-M[nums[i]] <= k)
11         return true;
12       else
13         M[nums[i]] = i;
14     }
15 
16     return false;
17   }
18 };