# 0220. 存在重复元素 III
### 题目地址(220. 存在重复元素 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
```
### 前置知识
* 哈希表
### 公司
* 暂无
### 暴力（超时）
#### 思路
最简单的思路就是双层循环，找出所有的两两组合。然后逐个判断其是否满足 `nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。`
#### 代码
```python
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if abs(nums[i] - nums[j]) <= t and j - i <= k:
return True
return False
```
**复杂度分析**
* 时间复杂度：$O(N ^ 2)$
* 空间复杂度：$O(1)$
### 暴力 + 剪枝 （超时）
#### 思路
上述的内存循环可以稍微优化一下， 之前我们从 i + 1 到 len(nums)，实际上我们只需要 i + 1 到 min(len(nums), i + k + 1)。这样我们的 `j - i <= k` 也可以省略了。
#### 代码
```python
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
for i in range(len(nums)):
for j in range(i + 1, min(len(nums), i + k + 1)):
if abs(nums[i] - nums[j]) <= t:
return True
return False
```
**复杂度分析**
* 时间复杂度：$O(N ^ 2)$
* 空间复杂度：$O(1)$
### 分桶 （通过）
#### 思路
这道题是 [219. 存在重复元素 II](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/219.contains-duplicate-ii) 的进阶版。那道题的条件是 `nums[i] == nums[j]`, 而这道题则更加宽泛，是`nums [i] 和 nums [j] 的差的绝对值小于等于 t` 。
这里我们介绍一种分桶的思想，其基本思想和桶排序是类似的。
具体来说，我们可使用 (t + 1) 个桶。将所有数除以 (t+1) 的结果**作为编号存到一个哈希表中**，不难知道哈希表的编号范围为 \[0, t]，因此哈希表最大容量为 (t+1)。
经过这样的处理，如果两个数字的编号相同，那么意味着其绝对值差小于等于 t。
那么如果两个数字的编号不同，是否意味着其绝对值差大于 t 呢？也不一定，**相邻编号**也可能是绝对值差小于等于 t 。因此我们只需要检查以下三种情况即可。
1. 当前编号
2. 左边相邻的编号
3. 右边相邻的编号
另外由于题目限定是索引差小于等于 k，因此我们可以固定一个窗口大小为 k 的滑动窗口，每次都仅处理窗口内的元素，这样可以保证桶内的数任意两个数都满足**索引之差的绝对值小于等于 k**。 因此我们需要清除哈希表中过期（不在窗口内）的信息。
具体算法：
* 我们将数据分到 M 个桶 中。
* 每个数字 nums\[i] 都被我们分配到一个桶中
* 分配的依据就是 nums\[i] // (t + 1)
* 这样相邻桶内的数字最多相差`2 * t + 1`
* 不相邻的桶一定不满足相差小于等于 t
* 同一个桶内的数字最多相差`t`
1. 因此如果命中同一个桶内，那么直接返回 True
2. 如果命中相邻桶，我们再判断一下是否满足 相差 <= t
3. 否则返回 False
需要注意的是，由于题目有索引相差 k 的要求，因此要维护一个大小为 k 的窗口，定期清除桶中`过期`的数字。
#### 关键点
* 分桶排序思想的应用
#### 代码
我们使用哈希表来模拟桶，key 就是桶号，value 就是数字本身。
Python 3:
```python
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]
if i >= k: bucket.pop(nums[i - k] // (t + 1))
return False
```
C++
```
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
if(t<0) return false;
//t+1可能会溢出，所以要+ 1LL
long long mod = t + 1LL;
unordered_map buck;
for(int i=0;i= k)
{
long long pos = nums[i - k] / mod;
if(nums[i - k] < 0) pos--;
buck.erase(pos);
}
}
return false;
}
};
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：由于过期的会被清除，因此哈希表大小不会大于 k，因此空间复杂度为 $O(min(n,k))$
### 扩展
实际上我们也可以一次遍历，并将遍历到的数字全部放到平衡二叉搜索树。这样我们只需要查找一下是否存在一个 x，满足 nums\[i] - t <= x <= nums\[i] + t 即可。
当然，我们仍然需要像方法三（桶排序）那样将过期的数排除。我们可以调用二叉平衡的删除方法。不过这种做法时间和空间并不优秀，给大家做扩展思路好了。
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
