題目描述:給定一個整數陣列 nums 和整數 k,判斷是否存在兩個不同的索引 i 和 j,使得 nums[i] == nums[j] 且 |i - j| <= k。換句話說,就是在大小為 k 的滑動視窗中,是否出現過重複的數字。
解題思路:使用滑動視窗搭配雜湊集合(Hash Set)。維護一個最多包含 k 個元素的集合,代表當前視窗內的所有數字。對每個新元素,先檢查它是否已在集合中——若在,表示視窗內有重複,直接回傳 true;若不在,將其加入集合。當視窗大小超過 k 時(即 i > k),移除最左側的元素 nums[i - k] 以維持視窗大小。若遍歷完整個陣列都沒有找到重複,回傳 false。這種方式保證集合中任意兩個元素的索引距離都不超過 k。
時間複雜度:O(n) — 只需遍歷陣列一次,每次對雜湊集合的插入、查找、刪除操作平均都是 O(1),因此整體為線性時間。
空間複雜度:O(k) — 雜湊集合最多同時存放 k 個元素,額外空間與視窗大小成正比。
1. Initialize an empty hash set `window`. 2. For each index i from 0 to n-1: a. If nums[i] is already in `window`, return true. b. Insert nums[i] into `window`. c. If the size of `window` exceeds k, remove nums[i - k] from `window`. 3. Return false.
方法一:暴力雙迴圈(Brute Force) 對每個元素,向後檢查最多 k 個元素是否有相同值。時間複雜度 O(n·k),空間複雜度 O(1)。當 k 很大時效率極差,不推薦。
方法二:雜湊表記錄最後出現索引(HashMap with Last Index)
使用 unordered_map<int, int> 記錄每個值最後一次出現的索引。對每個元素,若 map 中已存在該值且當前索引與記錄索引之差 ≤ k,則回傳 true;否則更新索引記錄。時間複雜度 O(n),空間複雜度 O(n)(最壞情況下所有元素都不同)。與滑動視窗解法思路不同但效果相同,空間使用略多。
|nums[i] - nums[j]| <= t(值的差距也有限制),也就是 LeetCode 220 Contains Duplicate III,該如何設計更高效的解法?