【力扣题】题目描述:
【Python3】代码:
1、解题思路:哈希表。遍历每个元素,将元素及下标添加到字典,若当前元素已在字典中且下标之间距离k,则存在重复元素。
知识点:{}:创建空字典。
enumerate(序列):返回可遍历的元素的下标及元素,(下标,元素)为元组形式。
字典[键]:通过键获取值,若没有该键,则添加键值对。
键 in 字典:判断键是否在字典中。判断值是否在字典中则使用:值 in 字典.values()。
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:# 哈希表d = {}for i,x in enumerate(nums):if x in d and i - d[x] <= k:return Trued[x] = ireturn False
2、解题思路:滑动窗口。遍历每个元素,用集合记录连续的k个元素(即下标为i-k到i)作为滑动窗口,判断滑动窗口中是否有重复元素。
知识点:set():创建空集合。
集合.remove(...):从集合中移除元素。
集合.add(...):往集合中添加元素。
注解:i<=k时,若存在重复元素,返回True,若没有重复的元素,将元素添加到集合中;i>k时,将下标为i-k-1的元素从集合中移除,使滑动窗口始终保持k位(即下标为i-k到i的k个元素),判断滑动窗口中是否有重复元素即可。
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:# 滑动窗口s = set()for i,x in enumerate(nums):if i > k:s.remove(nums[i-k-1])if x in s: return Trues.add(x)return False