【面试经典150 | 哈希表】存在重复元素 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了【面试经典150 | 哈希表】存在重复元素 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

【哈希表】【滑动窗口】【数组】

题目来源

219. 存在重复元素 II

【面试经典150 | 哈希表】存在重复元素 II,面试经典150题,哈希表,滑动窗口,数组

题目解读

判断在数组中有没有相同的元素小于一定的距离。

解题思路

方法一：哈希表

我们维护一个哈希表来记录数组中的元素以及上一次出现的位置，如果上一次出现的位置和这一次出现的位置之差小于等于 k，那就返回 true，否则返回 false。

实现代码

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();

        unordered_map<int, int> mp;
        for (int i = 0; i < n; ++i) {
            if (mp.count(nums[i]) && (i - mp[nums[i]] <= k)) {
                return true;
            }
            mp[nums[i]] = i;
        }
        return false;
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 为数组 nums 的长度。

空间复杂度： $O (n)$ ，使用哈希表记录数组中元素上一次出现的位置。

方法二：滑动窗口

换一个思路，我们只要判断在长度为 k 的窗口中是否有重复的元素出现即可。在滑窗没满之前，就向滑窗中加入元素，加入之前判断滑窗内是否有当前要加入的元素，如果有，直接返回 false；当滑窗满了，滑动滑窗，当前的 nums[i] 要进入滑窗，那么 nums[i - k - i] 要退出滑窗，判断滑窗内是否有当前要加入的元素，如果有，直接返回 false。

如果滑窗滑到数组末尾，都没有返回 true，就返回 false。

实现代码

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

时间复杂度： $O (n)$ ， $n$ 为数组 nums 的长度。

空间复杂度： $O (k)$ ，使用无序集合记录滑窗中的元素。

其他语言

python3+哈希表

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = {}
        for i, num in enumerate(nums):
            if num in pos and i - pos[num] <= k:
                return True
            pos[num] = i
        return False

python3+滑动窗口

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        s = set()
        for i, num in enumerate(nums):
            if i > k:
                s.remove(nums[i - k - 1])
            if num in s:
                return True
            s.add(num)
        return False