0220. 存在重复元素 III

题目地址(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 之间的差的绝对值最大为 ķ。

代码

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 也可以省略了。

代码

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 的进阶版。那道题的条件是 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:

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<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)
            {
                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 即可。

当然，我们仍然需要像方法三（桶排序）那样将过期的数排除。我们可以调用二叉平衡的删除方法。不过这种做法时间和空间并不优秀，给大家做扩展思路好了。

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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