存在重复元素 II

题目：

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例：

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

解题方法：

这道题先介绍一下我的解题思路：

• 首先要找到重复出现的数字，需要对数组中的数字进行统计，所以使用了map数据类型；
• 遍历map，找到出现次数大于1的数字
• 将重复出现的数字的索引存进一个数组中，并统计相邻两个索引的差值是否满足要求。

代码和结果：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        map<int,int> tb;
        for(int i=0;i<nums.size();i++)
        {
            tb[nums[i]]++;
        }

        for(map<int,int>::iterator it=tb.begin();it!=tb.end();it++)
        {
            if(it->second>1)
            {
                vector<int> idx;
                for(int i=0;i<nums.size();i++)
                {
                    if(nums[i]==it->first)
                    {
                        idx.push_back(i);
                    }
                }
                
                for(int i=0;i<idx.size()-1;i++)
                {
                    if(idx[i+1]-idx[i]<=k)
                    {
                        return true;
                    }
                }
            }
        }

        return false;
    }
};

运行结果:

这个方法还是有点繁琐的，操作越多出错的概率就越大，所以上面的方法是最容易想到的，但也是操作难度比较大的，并且就结果而言，也不是很好。通过学习Leetcode上的题解，get到了一个更妙的方法：

• 创建一个set用来保存搜索窗内(len=k)数据；
• 如果当前数组值可以在set内找到，说明有符合要求的重复数据；
• 如果在set中找不到，就插入set中，然后判断数组数组是否超出搜索窗长度，如果超出了，就删除set中第一个插入的数值。

代码和结果：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        set<int> tb;
        for(int i=0;i<nums.size();i++)
        {
            if(tb.find(nums[i])!=tb.end())
                return true;
            tb.insert(nums[i]);
            if(tb.size()>k)
                tb.erase(nums[i-k]);
        }

        return false;    
    }
};

运行结果:

难受，虽然是按照大佬们的思路来实现的，但是效果确实不怎么样！

原题链接：https://leetcode-cn.com/problems/contains-duplicate-ii/