存在重复元素III
题目链接 给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ， 同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例:
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
思路
等价于对于位置i,求下标范围为[max(0,i-k), i]找到值范围在[v - t, v + t]的数
解法一：
每次遍历到位置i时，往后检查k个元素（此过程需要高效查询、插入与删除操作）。
from sortedcontainers import 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
解法二：
桶的大小设置为 t+1。我们将元素按照大小依次放入不同的桶中。
遍历数组 nums 中的元素，对于元素 nums[i] ：
- 如果 nums[i] 放入桶之前桶里已经有元素了，那么这两个元素必然满足 abs(nums[i] - nums[j]) <= t，
- 之前桶里没有元素，那么就将 nums[i] 放入对应桶中。
- 再判断左右桶的左右两侧桶中是否有元素满足 abs(nums[i] - nums[j]) <= t。
- 将 nums[i-k] 之前的桶清空，因为这些桶中的元素与 nums[i] 已经不满足 abs(i - j) <= k 了。
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
bucket_dict = dict()
for i in range(len(nums)):
# 将 nums[i] 划分到大小为 t + 1 的不同桶中
num = nums[i] // (t + 1)
# 桶中已经有元素了
if num in bucket_dict:
return True
# 把 nums[i] 放入桶中
bucket_dict[num] = nums[i]
# 判断左侧桶是否满足条件
if (num - 1) in bucket_dict and abs(bucket_dict[num - 1] - nums[i]) <= t:
return True
# 判断右侧桶是否满足条件
if (num + 1) in bucket_dict and abs(bucket_dict[num + 1] - nums[i]) <= t:
return True
# 将 i-k 之前的旧桶清除，因为之前的桶已经不满足条件了
if i >= k:
bucket_dict.pop(nums[i-k] // (t + 1))
return False