219. Contains Duplicate II---数组中两个重复的数字的下标最多相差k

本文主要是介绍219. Contains Duplicate II---数组中两个重复的数字的下标最多相差k，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 absolute difference between i and j is at most k.
方法一、hash

bool containsNearbyDuplicate(vector<int>& nums, int k)
{int len = nums.size();if(len<0){return false;}map<int,int> mp;for(int i=0; i<len; i++){if(mp.find(nums[i]) != mp.end()){if((i-mp[nums[i]])<=k){return true;break;}else{mp[nums[i]] = i;}}else{mp.insert(pair<int,int>(nums[i],i));}}return false;
}

方法二、集合的方法

bool containsNearbyDuplicate(vector<int>& nums, int k) {set<int> cand;for (int i = 0; i < nums.size(); i++) {//首先将前面的k+1个数字先插入进集合中，集合的性质是里面的所有数字都不会重复if (i > k) cand.erase(nums[i-k-1]); /*insert(key_value); 将key_value插入到set中 ，返回值是pair<set<int>::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的key_value在set中的位置。inset(first,second);将定位器first到second之间的元素插入到set中，返回值是void.*/if (!cand.insert(nums[i]).second) return true;}return false;}

这篇关于219. Contains Duplicate II---数组中两个重复的数字的下标最多相差k的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---