> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/multiple-pointers/sliding-window/static-size/contains-duplicate-iii.md).

# Contains Duplicate III

<https://leetcode.com/problems/contains-duplicate-iii/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.

## Thoughts

查任意长度为k的subarray是否包含两个元素的差<=t. brute force是维持长度为k的滑动窗口, 和一个set, 每次右移动, 检查Set中是否包含\[num - t, num+t]中的任意一个数. TLE. \[<https://www.hrwhisper.me/leetcode-contains-duplicate-i-ii-iii/>].

可以把set换成tree set存储和检查范围. 除此之外还可以用Buckts sort的思想, 把Set替换成一堆bucket, 每个bucket存范围在t + 1之间的数. 对于一个数, 将它分到第num / (t + 1)个桶中. 比如t =3, 那么\[0, 1, 2, 3]存在0号bucket, \[4, 5, 6, 7]存在1号桶, \[8, 9, 10, 11]在2号桶 依次类推. 这里桶的范围是t+1以避免出现t=0时的情况. 现在对于num, 检查当前窗口中是否有范围在\[num - t, num + t]内的元素, 如果有这么一个数, num2, 它可能是三种情况之一, 在同一个bucket(比如0, 3); num在bucket靠右, num2在bucket + 1的桶里(比如3, 7); num1靠左, num2在bucket - 1里(比如5, 1). 因此我们维护一个map, key作为bucket index, val为窗口中在该bucket的元素, 对元素, 不用set. 比如num = 5, 之前出现了8, 然后被10覆盖, 乍看上去5和10不在t中, 答案不对. 但当10出现时, 10和8就在同一个桶中, 已经查出来了, 所以不会出现错误.

## Code

```
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) {
            return false;
        }

        Map<Long, Long> map = new HashMap<>();
        long div = (long)t + 1;
        for (int i = 0; i < nums.length; i++) {
            long num = (long)nums[i];
            long bucket = num / div;
            if (num < 0) {
                bucket--;
            }
            if (map.containsKey(bucket)
               || map.containsKey(bucket + 1) && map.get(bucket + 1) - num <= t
               || map.containsKey(bucket - 1) && num - map.get(bucket - 1) <= t) {
                return true;
            }
            if (i >= k) {
                map.remove((long)nums[i - k] / div);
            }
            map.put(bucket, num);
        }

        return false;
    }
}
```

## Analysis

时间复杂度O(N).