https://leetcode-cn.com/problems/contains-duplicate-iii/
在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
如果存在则返回 true，不存在返回 false。
示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false
- 哈希表
- 暂无
这道题是 219. 存在重复元素 II 的进阶版。那道题的条件是 nums[i] == nums[j], 而这道题则更加宽泛，是nums [i] 和 nums [j] 的差的绝对值小于等于 t 。
这里我们介绍一种分桶的思想，其基本思想和桶排序是类似的。
具体来说，我们可使用 t 个桶。将所有数除以 (t+1) 的结果作为编号都存到一个哈希表中，不难知道哈希表的大小为 t。如果两个数字的编号相同，那么意味着其绝对值差小于等于 t。
那么如果两个数字的编号不同，是否意味着其绝对值差大于 t 呢？也不一定，相邻编号也可能是绝对值差小于等于 t 。因此我们只需要检查以下三种情况即可。
- 当前编号
- 左边相邻的编号
- 右边相邻的编号
另外由于题目限定是索引差小于等于 k，因此需要清除哈希表中过期的信息。
- 分桶排序思想的应用
- 语言支持：Python3
Python3 Code:
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
bucket = dict()
if t < 0:
return False
for i in range(len(nums)):
nth = nums[i] // (t + 1)
if nth in bucket:
return True
if nth - 1 in bucket and abs(nums[i] - bucket[nth - 1]) <= t:
return True
if nth + 1 in bucket and abs(nums[i] - bucket[nth + 1]) <= t:
return True
bucket[nth] = nums[i]
# 如果数组有相同的数会有影响么？答案是不会，因为如果有相同的数，我们直接就会在前面返回 true 了。
if i >= k:
bucket.pop(nums[i - k] // (t + 1))
return False复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：由于过期的会被清除，因此哈希表大小不会大于 k，因此空间复杂度为
$O(min(n,k))$
此题解由 力扣刷题插件 自动生成。
力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
