## 题目地址(220. 存在重复元素 III)

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
```

## 前置知识

- 哈希表

## 公司

- 暂无

## 暴力（超时）

### 思路

最简单的思路就是双层循环，找出所有的两两组合。然后逐个判断其是否满足 `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://github.com/azl397985856/leetcode/blob/master/problems/219.contains-duplicate-ii.md) 的进阶版。那道题的条件是 `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++

```c++
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(t<0) return false;
        //t+1可能会溢出，所以要+ 1LL
        long long mod = t + 1LL;
        unordered_map<long long,long long> buck;
        for(int i=0;i<nums.size();i++)
        {
            long long nth = nums[i] / mod;
            //可能nums[i]为负数，比如-4 / 5 以及 -4 / 5都等于0，所以负数要向下移动一位
            if(nums[i] < 0) nth--;
            //这里要用find 不能直接[],因为可能本身存储的数字就为0
            if(buck.find(nth)!=buck.end())
                return true;
            else if(buck.find(nth-1)!=buck.end() && abs(nums[i] - buck[nth-1]) <= t)
                return true;
            else if(buck.find(nth+1)!=buck.end() && abs(nums[i] - buck[nth+1]) <= t)
                return true;
            buck[nth] = nums[i];
            if(i >= k)
            {
                buck.erase(nums[i - k] / mod);
            }
        }
        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 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
