给定一个包含多个重复元素的未排序的数组。另外给定一个数字k，且k小于数组大小。判断数组中是否包含重复元素，且它们相隔的距离处于范围k之内。例如:Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}Output: false所有重复元素的距离>k.Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}Output: true存在重复元素1,且距离为3(==k).Input: k = 3, arr[] = {1, 2, 3, 4, 5}Output: false没有重复元素Input: k = 3, arr[] = {1, 2, 3, 4, 4}Output: true存在重复元素4,且距离为1(<k)方法1(简单方法)使用两个循环. 外层循环依次遍历数组的所有元素arr[i]，做为起始元素，而内层循环将与arr[i]距离处于k范围内的所有元素与之比较，检测是否相等。此方法时间复杂度为O(k*n).方法2(使用哈希)时间复杂度：Θ(n)时间整体思路是将元素加入到哈希表中。然后将与当前元素间距大于k的元素删除掉。下面是具体算法。1) 创建空的哈希表.2) 从左至右遍历所有元素。假设当前元素为arr[i]。 a) 如果当前元素‘arr[i]’出现在哈希表中，，则返回true。 b) 否则将arr[i]添加到哈希表中，如果i大于等于k, 则将arr[i-k]从哈希表中删除。代码实现：#if __GNUC__>2#include <ext/hash_set>#include <ext/hash_map>using namespace __gnu_cxx;#else#include <hash_set>#include <hash_map>using namespace stdext;#endif#include <iostream>bool findDuplicatesWithinKDistrance(const int *arr, int arrSize, int k){hash_set<int> set;for (int i = 0; i<arrSize; i++){if (set.find(arr[i]) != set.end())return true;set.insert(arr[i]);//只比较当前元素与其前面的k个元素，更前面的则删除之，因为距离已经大于k了。if (i >= k)set.erase(arr[i – k]);}return false;}int main(){const int arrSize = 7;const int k = 3;int arr[arrSize] = { 11, 55, 22, 44, 22, 55, 77 };if (findDuplicatesWithinKDistrance(arr, arrSize, k))std::cout << "exist duplicates" << std::endl;elsestd::cout << "not exist duplicates" << std::endl;return 1;}输出：exist duplicates
那么，不如我们礼貌地保持相对距离，不至于太冷，不至于太痛。
