Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { multimap<int, int> cpy; if(nums.empty()) return false; int i = 0; for(auto num : nums) { if(cpy.find(num) != cpy.cend()) { auto bound = cpy.equal_range(num); while(bound.first != bound.second) { int j = bound.first->second; if(i - j <= k) return true; else bound.first++; } } cpy.insert({num, i++}); } return false; } };
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { map<int, int> buf; int n = nums.size(); for (int i = 0; i < n; i++) { if (buf.find(nums[i]) != buf.end() && i-buf[nums[i]] <= k) return true; else buf[nums[i]] = i; } return false; } };
原文：http://www.cnblogs.com/dylqt/p/4887987.html