> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0220_contains_duplicate_iii/slt.md).

# 思路1

我们换种思路。 由于本题对索引有要求，因此直接排序破坏了原来的索引的做法是不行的。 我们考虑使用桶排序。

我们将数据分到 M 个桶 中。

每个数字nums\[i] 都被我们分配到一个桶中 分配的依据就是 nth = nums\[i] // (t + 1)\
nth分别是(t+1)的0倍，1倍，2倍...

这样相邻桶内的数字最多相差2 \* t + 1 如t = 3, t+1 = 4 第一个桶：0,1,2,3, 第二个桶：4,5,6,7

最多相差7，就是2t + 1

不相邻的桶一定不满足相差小于等于t

同一个桶内的数字最多相差t

因此如果命中同一个桶内，那么直接返回True，即一个桶中有多个

如果命中相邻桶，我们再判断一下是否满足 相差 <= t 否则返回False

需要注意的是，由于题目有索引相差k的要求，因此要维护一个大小为k的窗口，定期清除桶中过期的数字。

代码 我们使用哈希表来模拟桶，key就是桶号，value就是数字本身。