日野弥生：勉強しよう
LeetCode 219 - 存在重复元素 II
发表于2025年04月06日
使用滑动窗口 + 有序集合的方式能更快速地处理此问题。
涉及索引范围的固定性，滑动窗口是最优选择。通过考虑到滑动窗口需要频繁查询和插入删除操作，红黑树的底层也符合需求。不过Python3有有序列表结构，可以支持二分查找和插入删除有序，可以直接使用。
为什么不直接用 heapq 或 list.sort()？
heapq 是堆，仅能获取最小/最大，不能二分查找、删除任意值。
list.sort() 会全量排序，开销大，不适合插入时排序。
SortedList结合了两者优点，自动排序且支持二分操作，非常适合滑动窗口类题目。
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
# O(N logk)
window = SortedList()
for i in range(len(nums)):
# len(window) == k，维护滑动窗口大小
if i > k:
window.remove(nums[i - 1 - k])
# 插入自动排序
window.add(nums[i])
# 二分查找索引
idx = bisect.bisect_left(window, nums[i])
# 找出满足条件的元素直接返回，剪枝
if idx > 0 and abs(window[idx] - window[idx-1]) <= t:
return True
if idx < len(window) - 1 and abs(window[idx+1] - window[idx]) <= t:
return True
return False