力扣每日一题-第29天-219.存在重复元素Ⅱ

2022.6.3今天你刷题了吗？

---

题目：

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

分析：

在一个数组里面，存在有一种重复元素，其个数>=2，我们要做的就是判断这个重复元素下标之差最小的是不是满足题目要求的k，存在下面特殊情况

0，1，2，0，0

这种情况，重复元素最小差为 1，也就是数组最后两个指下标做差

因此，结题思路就是最简单的暴力求解，我们依次遍历数组，求出每个重复元素之间的下标差，然后利用min函数求出最小，再进行比较就可以进行判断了。

解析：

1.暴力求解

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int inf = 1e9;
        int res = inf;
        for (auto i=0;i<nums.size()-1;++i)
        {
            for (auto j = i + 1; j < nums.size(); ++j)
            {
                if (nums[i] == nums[j])
                {
                    res = min(res, j - i);
                }
            }
        }
        if (res <= k)
        {
            return true;
        }
        else
        {
            return false;
        }
        return 0;
    }
};

2.哈希表

对于数组重复元素问题，哈希表是个好东西！！！

我们可以遍历一次数组，每次遍历时把数据按照（数值，下标）存入map，然后下次遍历的时候判断map里面是否已经存在该元素，如果存在并且下标条件满足则直接返回true，否则继续插入

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> map;

        for (auto i=0;i<nums.size();i++)
        {
            int num = nums[i];
            if (map.count(num) && i - map[num] <= k)
            {
                return true;
            }
            map[num] = i;
        }
        return false;

    }
};

3.滑动窗口

思想：由于给定k，那么我只需要判断k+1个数里面是否存在重复元素，如果存在，则必定返回true，如果不存在，则窗口移动，此时删除第一个元素，插入最后一个元素，再次判断是否存在重复的值。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int>set;
        for (auto i = 0; i < nums.size(); ++i)
        {
            if (i > k)
            {
                set.erase(nums[i - k - 1]);
            }
            if (set.count(nums[i]))
            {
                return true;
            }
            set.emplace(nums[i]);
        }
        return false;
    }
};