日野弥生：勉強しよう
LeetCode 219 - 存在重复元素 II
发表于2025年04月01日
利用二叉搜索树的方式自然是能解决此题，但是会时间超限。因为本题对顺序没有要求，哈希表或者滑动窗口是更好的选择。
class TreeNode:
def __init__(self, val=0, index=0, left=None, right=None):
self.val = val
self.index = index
self.left = left
self.right = right
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
self.tree = None
result = False
def createTree(root, val: int, index: int):
nonlocal result
if not root:
root = TreeNode(val, index)
return root
if val < root.val:
root.left = createTree(root.left, val, index)
elif val > root.val:
root.right = createTree(root.right, val, index)
else:
if not result:
result = True if abs(root.index - index) <= k else result
root.index = index
return root
for idx, val in enumerate(nums):
self.tree = createTree(self.tree, val, idx)
return result哈希表的方式
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
dic = {}
for idx, num in enumerate(nums):
if num in dic:
if abs(dic[num] - idx) <= k:
return True
else:
dic[num] = idx
else:
dic[num] = idx
return False