219. 存在重復元素 II

Level: Easy

方法一：滑動窗口

仍然采用預處理 + 部分遍歷的方式。首先遍歷nums數組中前k個元素，即位序[0, k]，將其存入集合，若遍歷過程中存在重復元素則直接返回True。

然后遍歷剩下的元素，直接判斷當前元素是否在集合中，特別注意，由于預處理數組長度已經為 k + 1，判斷存在性時，相當于向預處理數組再插入一個元素，此時數組長度已經為k + 2, 因此需要在判斷前，刪除數組左端點的元素。

Python版本

C++版本

復雜度分析

• 時間復雜度：O(N)。此處的 n 指的是數組 nums長度。

• 空間復雜度：O(K)。 自始至終維護一個大小為 k 的集合。

方法一優(yōu)化：遍歷合并+邊界檢查

此題求存在性，若數組中元素各不相同，則一定沒有滿足要求的位序對；

前 k + 1長度數組，其遍歷中的元素添加與成員判斷，可以合并到一次遍歷中；

Python版本

C++版本

備注

• 做題時，未充分考慮此題的特殊性，首先題目看似是一個不定長數組，但實際上仍然可以用滑窗，只需要保證最壞情況成立，即可保證成立

• 有兩點是沒有考慮到的：

• 遍歷前 k + 1 個元素，仍然可能遇到相同的元素

• 修改彈窗時，不應該按照傳統(tǒng)的左邊出隊，右邊入隊的思路，還需要考慮此時數組長度，顯然此題判斷時，數組長度已經為 k + 1, 不滿足判斷的元素之相對位置小于等于k的要求，因此需要先刪除左端點對應的元素后判斷。

• 做題應當首先考慮數據特性，選擇合適的數據類型，本題中選擇列表和集合無本質區(qū)別，至少是可變數據類型，因為本題會涉及到插入刪除，因為之所以用集合會出錯，是因為沒有處理同值下標。

• 查看復雜度排名時，發(fā)現邊界條件沒有考慮到，將數組轉換為集合，集合的容積如果與原數組相等則說明整個數組無重復元素，直接可以判定為錯誤

• 難點：以滑動窗口長度為 k + 1，舉例，此時刪除的元素應該是 nums[i - k - 1],因為題目限制的滑動窗口不是數組長度，而是位序長度，兩者差值為1。