滑动窗口秒存在重复元素 II

前言

大家好，我是熊哥，来自华为。今天给大家带来一道与滑动窗口和查找表相关的题目，这道题同时也是 airbnb 和 Palantir 的面试题，即力扣上的第219题-存在重复元素 II。

本文主要介绍滑动窗口加哈希表的策略来解答此题，供大家参考，希望对大家有所帮助。

存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，

使得 nums[i] = nums[j]，并且 i 和 j 的差的绝对值至多为 k。


示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:

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

解题思路

在数组中查找两个相等元素并使得其下标之差的绝对值不大于给定值，首先可以想到暴力法去求解，两层遍历数组，查找相等元素对并判断其下标之差的绝对值是否小于等于给定值，此解法的时间复杂度为O(n^2)。

对滑动窗口有所了解的童鞋，也会想到通过滑窗去做。

假设下标 i 和 j 对应的元素都相等，且 j - i ≤ k，如下图示：

示例

由于 j - i ≤ k，则 j 和 i 一定在一个区间中，假设区间为[len, len + k]，区间中共有 k + 1 个元素。

满足条件下标存在的区间

在连续的有 k + 1 个元素的区间中，若能找到两个元素其值相等，则能保证其对应下标的差一定小于等于 k。

问题转化为在数组中是否能找到一个 k + 1 的区间，满足区间中的两元素相等。

假如当前区间中，没有相等的两元素，则向右拓展，查看下一元素；同时减去第一个元素，len 右移动。

区间中不存在相等元素

向右拓展同时，len 右移

查看下一元素 m 在区间[len + 1, len + k]中是否有相同的元素。

判断下一元素是否跟区间中的元素相同

m 在区间中无相同元素的处理完整过程，如下动图示：

查找的完整过程

Show me the Code

「C++」

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    /* 创建查找表，滑窗的长度为查找表的长度 */
    unordered_set<int> record;  
    for (int i = 0; i < nums.size(); ++i) {
        /* 遍历数组时，查找该元素是否在查找表中 */
        if (record.find(nums[i]) != record.end()) {
            return true;
        }

        /* 拓展的下一元素跟区间元素不相等，将其纳入区间中*/
        record.insert(nums[i]);
        /* 查找表的长度超过 k，删除最左侧元素 */
        if (record.size() > k) {
            record.erase(nums[i - k]);
        }
    }

    return false;
}

「Java」

boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> record = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (record.contains(nums[i])) {
            return true;
        }

        record.add(nums[i]);
        if (record.size() > k) {
            record.remove(nums[i - k]);
        }
    }
    return false;
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度，需要遍历一遍数组。

空间复杂度：O(k)。

本文由哈喽比特于3年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/kVDYwTPCLFW3CGb2KewA0g