【LeetCode】219.存在重复元素II
1. 题目
2. 分析
3. 代码
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:num2index = defaultdict(list)for idx,num in enumerate(nums):num2index[num].append(idx)for key, val in num2index.items():if len(val) >= 2:for i in range(len(val)-1):nex = val[i+1]if abs(nex - val[i]) <= k:return Truereturn False
上面这版代码空间复杂度还不是最优，原因是存储了非窗口内的元素。最优解的做法是：在滑动窗口的过程中动态的维护一个哈希表，哈希表中存储的内容是某个元素上一次出现的下标。 我记得滑动窗口类的题目好多都是这种做法。