leetcode-219-Contains Duplicate II（使用set来判断长度为k+1的闭区间中有没有重复元素）
leetcode-219-Contains Duplicate II（使用set来判断长度为k+1的闭区间中有没有重复元素）
题目描述：
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.
Example 1:
Input: [1,2,3,1], k = 3
Output: trueExample 2:
Input: [1,0,1,1], k =1
Output: trueExample 3:
Input: [1,2,1], k =0
Output: false要完成的函数：
bool containsNearbyDuplicate(vector<int>& nums, int k)
说明：
1、这道题给定一个vector和一个整数k，要求判断能不能找到两个不同位置的相同元素，他们的位置分别是i和j，使得i-j的绝对值不超过k。
2、这道题相比起上一道“找到两个重复的元素”，增加了距离k的限制。
首先，我们能够判断如果k<=0，那么必定是不存在两个不同位置的相同元素的。
其次，如果k>=nums.size()-1，那么这道题也就是上一道“找到两个重复的元素”的做法。
所以我们只需要关注k<nums.size()这种情况下，我们要如何判断。
最简单最暴力的方法当然是双重循环，设定窗口长度为k+1，从nums的第一位开始，判断窗口内有没有跟首元素相同的元素。
接着窗口不断往后挪，去掉第一个元素，增加一个新的元素，判断窗口的首元素，也就是这时候nums的第二个元素，有没有在窗口内出现重复元素。
这种做法时间复杂度O(n^2)
我们也可以仍然往后挪窗口，只不过使用set，用哈希的方法来判断窗口中有没有重复元素，这种判断比起上述暴力方法快了许多。
时间复杂度大致是O(n)，因为哈希的时间时间复杂度是O(1)？
代码如下：（附详解）
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
int s1=nums.size();
if(k<=0)//边界条件
return false;
if(k>=s1-1)//转化为上一道题，“找到两个重复的元素”
{
sort(nums.begin(),nums.end());
for(int i=0;i<s1-1;i++)
{
if(nums[i]==nums[i+1])
return true;
}
return false;
}
unordered_set<int>set1(nums.begin(),nums.begin()+k+1);//使用set来存储，初始化其中有k+1个元素
if(set1.size()!=k+1)//初始情况下的判断
return true;
for(int i=k+1;i<s1;i++)
{
set1.erase(nums[i-k-1]);//删去首位元素
set1.insert(nums[i]);//增加后一位新的元素，这个插入过程其实包含了判断有没有重复，决定要不要插入到set中
if(set1.size()!=k+1)//用set的size来判断
return true;
}
return false;
}上述代码实测24ms，beats 97.46% of cpp submissions。
腾讯云开发者
