滑動窗口秒存在重復元素 II

前言

大家好，我是熊哥，來自華為。今天給大家?guī)硪坏琅c滑動窗口和查找表相關的題目，這道題同時也是 airbnb 和 Palantir 的面試題，即力扣上的第219題-存在重復元素 II。

本文主要介紹滑動窗口加哈希表的策略來解答此題，供大家參考，希望對大家有所幫助。

存在重復元素 II

給定一個整數(shù)數(shù)組和一個整數(shù) k，判斷數(shù)組中是否存在兩個不同的索引 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

解題思路

在數(shù)組中查找兩個相等元素并使得其下標之差的絕對值不大于給定值，首先可以想到暴力法去求解，兩層遍歷數(shù)組，查找相等元素對并判斷其下標之差的絕對值是否小于等于給定值，此解法的時間復雜度為O(n^2)。

對滑動窗口有所了解的童鞋，也會想到通過滑窗去做。

假設下標 i 和 j 對應的元素都相等，且 j - i ≤ k，如下圖示：

由于 j - i ≤ k，則 j 和 i 一定在一個區(qū)間中，假設區(qū)間為[len, len + k]，區(qū)間中共有 k + 1 個元素。

在連續(xù)的有 k + 1 個元素的區(qū)間中，若能找到兩個元素其值相等，則能保證其對應下標的差一定小于等于 k。

問題轉化為在數(shù)組中是否能找到一個 k + 1 的區(qū)間，滿足區(qū)間中的兩元素相等。

假如當前區(qū)間中，沒有相等的兩元素，則向右拓展，查看下一元素；同時減去第一個元素，len 右移動。

查看下一元素 m 在區(qū)間[len + 1, len + k]中是否有相同的元素。

完整過程，如下動圖示：

Show me the Code

「C++」

bool containsNearbyDuplicate(vector<int>& nums, int k) {
    /* 創(chuàng)建查找表，滑窗的長度為查找表的長度 */
    unordered_set<int> record;  
    for (int i = 0; i < nums.size(); ++i) {
        /* 遍歷數(shù)組時，查找該元素是否在查找表中 */
        if (record.find(nums[i]) != record.end()) {
            return true;
        }

        /* 拓展的下一元素跟區(qū)間元素不相等，將其納入區(qū)間中*/
        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 是數(shù)組的長度，需要遍歷一遍數(shù)組。

空間復雜度：O(k)。

滑動窗口往期精彩回顧

字符串最長子串難？滑動窗口拯救你

臉書面試題 leetcode 209. 長度最小的子數(shù)組(滑動窗口)

更多精彩

關注公眾號「程序員小熊」