靈感來源?
- 保持更新，努力學習
- python腳本學習
存在重復元素 II
解題思路
這個問題可以通過哈希表來高效解決。具體思路如下：
- 使用哈希表記錄元素最后一次出現的位置：遍歷數組，用一個哈希表存儲每個元素的最后一次出現的索引。
- 檢查索引差：對于每個元素，如果它已經在哈希表中存在，計算當前索引與哈希表中存儲的索引的差值。如果這個差值小于等于給定的?
k，則返回?True。 - 更新哈希表：無論元素是否已經存在于哈希表中，都更新它的索引為當前索引。這樣可以確保哈希表中存儲的是元素最后一次出現的位置，從而使得后續的檢查能夠得到最小的索引差。
這種方法的時間復雜度是 O (n)，其中 n 是數組的長度，因為只需要遍歷一次數組。空間復雜度是 O (min (n, k))，因為哈希表中最多存儲 k+1 個元素。
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:# 用于存儲元素及其最后一次出現的索引num_dict = {}for i, num in enumerate(nums):# 如果元素已經在字典中，檢查索引差if num in num_dict and i - num_dict[num] <= k:return True# 更新元素的最后一次出現的索引num_dict[num] = ireturn False逐行解釋
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:# 創建一個字典，用于存儲每個元素及其最后一次出現的索引位置num_dict = {}# 遍歷數組中的每個元素及其索引for i, num in enumerate(nums):# 檢查當前元素是否已經在字典中，并且當前索引與上次出現的索引之差 <=kif num in num_dict and i - num_dict[num] <= k:return True # 找到滿足條件的重復元素，返回True# 更新字典中該元素的索引為當前索引（無論是否已存在，確保記錄最新位置）num_dict[num] = i# 遍歷結束后仍未找到滿足條件的重復元素，返回Falsereturn False
