> For the complete documentation index, see [llms.txt](https://kongchengzhuge.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kongchengzhuge.gitbook.io/leetcode/220.-contains-duplicate-iii.md).

# 220. Contains Duplicate III

## problem description

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums\[i] and nums\[j] is at most t and the absolute difference between i and j is at most k.

**Example 1:**

```
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
```

**Example 2:**

```
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
```

**Example 3:**

```
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
```

## algorithm thought

这是这个系列的第三题，第二题加入了k表示只看前面k个数。第三题加入了t，代表数字的范围可以再t以内波动。

最开始，我想的是，还是和前一题一样处理，只不过判断是是否存在的时候，使用一个for循环判断这个范围内的值。但是这个题目的测试样例很bug，有个测试样例是INT\_MAX，直接超时。

看了discuss，发现有人用桶的方法解这题，我感觉很巧妙。和之前桶排序一样。首先定下桶的大小，这里设为t+1。从INT\_MIN开始，每个桶只能放一个数。如果出现相同的桶，那么就可以直接返回true，因为同一个桶中，最大的差值就是t。然后还需要在这个桶的前一个和后一个桶中找数，判断差值是否小于t。如果存在，返回true。通过这种办法，将数字换成桶，再重复利用上题的算法，这里时间复杂度可以到O(n)

## code

```cpp
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(k<1||t<0)
            return false;
        unordered_map<long,long> ma(k);
        long tmp=static_cast<long>(t);
        for(int i=0;i<nums.size();++i){
            long bucket_num=(static_cast<long>(nums[i])-INT_MIN)/(tmp+1);
            if(ma.count(bucket_num)||
              (ma.count(bucket_num+1)&&ma[bucket_num+1]-nums[i]<=t)||
              (ma.count(bucket_num-1)&&nums[i]-ma[bucket_num-1]<=t))
                return true;
            ma[bucket_num]=nums[i];
            if(i-k>=0){
                ma.erase((static_cast<long>(nums[i-k])-INT_MIN)/(tmp+1)); 
            }
        }
        return false;
    }
};
```

## algorithm analysis

这里遍历一次数组得到结果，时间复杂度O(n)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/220.-contains-duplicate-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.