滑動窗口判斷是否存在重複元素

問題描述

來源：LeetCode 第 219 題

難度：簡單

給定一個整數數組和一個整數 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:

使用 Map 解決

上一題講過 607，位運算等多種方式判斷是否存在重複元素，不過上一題只需要判斷是否有重複元素即可，並沒有其他條件的限制。但是這題要求如果有相同的元素，這兩個元素的距離不能超過 k。

我們可以使用一個 Map，分別記錄數組中元素的值和他對應的下標，如果當前值在 Map 中出現過，我們就取出之前出現過的元素下標和當前元素的下標比較，如果差值不大於 k，直接返回 true。如果大於 k，說明他倆相距太遠，就繼續往下找……

public boolean containsNearbyDuplicate(int[] nums, int k) {
    //map中key存儲的是數組中的元素，value存儲的是
    //對應元素在數組中的下標
    Map<Integer, Integer> map = new HashMap<>();
    //遍歷數組中的所有元素
    for (int i = 0; i < nums.length; i++) {
        //判斷數組中是否出現過相同的元素nums[i]，如果出現
        //過就計算之前元素下標和當前元素下標的差值是否小於
        //等於k，如果小於等於k，直接返回true。
        if (map.containsKey(nums[i])) {
            int index = map.get(nums[i]);
            if (i - index <= k)
                return true;
        }
        //把當前元素及他的下標同時存儲到map中
        map.put(nums[i], i);
    }
    return false;
}

如果有重複的元素，那麼 map 的 put 方法會返回重複元素的下標，我們可以先把數組中的元素一個個存儲到 map 中，如果 put 方法返回不爲空，說明出現了重複的元素，所以上面的代碼還可以這樣寫。

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        //如果有重複的元素，put方法會把它覆蓋掉，並且返回
        //上一個元素的value值
        Integer index = map.put(nums[i], i);
        //如果index不爲空，說明出現過重複的元素，我們只需要
        //判斷這兩個元素的下標差值是否小於等於k即可。
        if (index != null && i - index <= k) {
            return true;
        }
    }
    return false;
}

滑動窗口解決

題中說了如果有相同的元素，還需要這兩個元素的距離不能超過 k，所以我們可以使用滑動窗口來解決，就是申請一個大小爲 k+1 的窗口，每次往窗口中添加元素的時候，如果窗口中元素的個數超過 k（也就是窗口滿了），就把最前面的給移除掉，然後再把當前元素添加到窗口中，最後判斷窗口中是否有重複的元素，如果有重複的直接返回 true，這裏隨便舉個例子，來看個視頻

視頻詳情

來看下代碼

public boolean containsNearbyDuplicate(int[] nums, int k) {
    //windowSet相當於一個窗口，窗口的大小是k+1
    Set<Integer> windowSet = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        //如果窗口中的元素個數超過k，就把最前面的給移除
        if (i > k) {
            windowSet.remove(nums[i - k - 1]);
        }
        //這個時候窗口中的元素都是不超過k+1的，然後我們判斷這個窗口
        //中是否有重複的元素
        if (!windowSet.add(nums[i]))
            return true;
    }
    return false;
}

截止到目前我已經寫了 600 多道算法題了，爲了方便大家閱讀，我把部分算法題整理成了 pdf 文檔，目前有 1000 多頁，大家可以在公衆號中回覆關鍵字 “pdf” 即可獲取下載鏈接。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/vbuP16jTFlPfRp31jjIAgA