LeetCode 220. 存在重复元素 III

2020-10-17 HGNULB 约 10 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 220. 存在重复元素 III

题意分析

问的是能否找到一对不同下标 i 和 j，同时满足两个「接近」条件：下标接近，abs(i - j) <= k；取值也接近，abs(nums[i] - nums[j]) <= t。只需要判断存在性，返回布尔值。

和只要求值完全相等的版本相比，这里的值条件从「等于」放宽成了「落进一个宽度为 2t 的区间」，这一放宽直接废掉了哈希表——哈希只能 $O(1)$ 回答「有没有这个键」，回答不了「有没有键落在某个范围里」。约束里出现区间查询，就是在要求一个支持按序查找的结构，或者一种能把区间查询降级成等值查询的编码。

下标条件仍然是「距离不超过 k」，这依然指向以当前位置为右端、长度最多 k + 1 的窗口，窗口内元素随扫描进出。

数据规模上数组长度可达 2×10^4，元素取值覆盖整个 int 范围且可为负，t 也可以取到 int 上界。值域跨满 int 意味着 x + t、x - t 都可能溢出 32 位，必须提升到 64 位计算；负数的存在意味着任何按值分段的做法都要单独处理向下取整的方向。

边界包括：t = 0 退化成要求值完全相等；k 大于等于数组长度时窗口覆盖全数组；数组长度为 1 时不存在任何合法下标对，必须返回 false。

解法：滑动窗口 + 有序集合

核心思路

暴力做法是对每个 i 往左看最多 k 个位置，逐个检查值差是否不超过 t，代价是 $O(nk)$。在 n 和 k 都接近 2×10^4 时是 4×10^8 次比较，瓶颈在于窗口内的元素每次都被线性重扫，而我们真正需要的只是「窗口里离 x 最近的那个值」，并不需要看遍所有元素。

观察点是：只要窗口里的元素能按值有序地组织起来，「是否存在值落在 [x - t, x + t]」就可以用一次查找解决——找到窗口中第一个不小于 x - t 的值，如果它同时不超过 x + t，说明命中；如果连这个最小的候选都已经越过了 x + t，那么比它更大的值只会更远，可以直接判否。这一步把窗口内的线性扫描压成了对数级查找。

由此确定不变量：处理下标 i 之前，有序集合中恰好装着下标区间 [i-k, i-1] 内的全部元素值。维护住这条不变量，每一步只需做一次范围查找、一次插入、一次过期删除。

集合中不会出现重复值这一点也是不变量的推论：一旦窗口里出现两个相等的值，它们的差为 0，必然满足 0 <= t，算法早就返回 true 了。所以用去重的有序集合是安全的，删除过期元素时也不会误删还该留着的同值副本。

Go 没有标准库的有序集合，这里用等价的桶划分实现同一个查询语义：把整条数轴按宽度 t + 1 切成一个个桶，落进同一个桶的两个数差值必然不超过 t，因此「同桶已有元素」直接判真；而差值不超过 t 却不同桶的两个数只可能相邻，于是再检查左右各一个相邻桶即可。桶到值的映射用哈希表存，由于同桶至多存一个值（存第二个之前就返回了），每次查询只看三个桶，是常数时间。

解题步骤

先做参数合法性判断，k <= 0 或 t < 0 时直接返回 false。之所以要判，是因为下标必须不同意味着距离至少为 1，k <= 0 时不存在任何可行对；而 t < 0 时值差的绝对值不可能为负，同样无解，提前返回也能避免后面用 t + 1 作桶宽时出现零或负数除数。

把元素值提升到 64 位再参与运算。之所以必须提升，是因为 x - t 在 x 接近 Integer.MIN_VALUE、t 接近 Integer.MAX_VALUE 时会向下溢出成一个巨大正数，边界判断会彻底反向。

从左到右扫描，在把当前值放进结构之前先做查询。之所以先查后插，是因为结构里此刻正好是下标区间 [i-k, i-1] 的元素，符合不变量；若先插入，当前元素会和自己配出差值 0，任何输入都被误判为 true。

有序集合版本用 ceiling(x - t) 取出集合中第一个不小于 x - t 的值，非空且不超过 x + t 就返回 true。之所以只需检查这一个候选，是因为它是所有大于等于下界的值里最小的，如果它都超过了上界，其余候选只会更大，无需再看。

桶版本先查同桶，再查左右相邻桶并显式验算差值。之所以相邻桶还要验算，是因为同桶保证差值不超过 t，但相邻桶只保证「有可能」接近，真实差值可能达到 2t，必须实测；也正因为只有相邻桶才可能藏着合法配对，检查三个桶就已穷尽。

查询未命中后把当前值写入结构。之所以写入的是当前值而不是标记，是因为下一轮的范围查询需要具体数值参与比较。

当 i >= k 时，把下标 i - k 处的元素从结构中移除。之所以门槛是 i >= k 而不是 i > k，是因为处理下标 i + 1 时合法窗口是 [i+1-k, i]，下标 i - k 已经出界，必须在本轮结束时清掉，否则下一轮会拿超距的元素配对。

扫描结束仍未命中则返回 false。

以 nums = [1, 5, 9, 1, 5, 9], k = 2, t = 3 走一遍有序集合版本。i = 0，x = 1，集合空，ceiling(-2) 为空，插入 1，集合 {1}，i < k 不删除。i = 1，x = 5，ceiling(2) 返回 5 之前集合只有 1，1 小于 2 所以返回空，未命中，插入 5，集合 {1, 5}。i = 2，x = 9，ceiling(6) 在 {1, 5} 中无解，返回空，插入 9 得 {1, 5, 9}，此时 i >= k，删除 nums[0] = 1，集合变为 {5, 9}。i = 3，x = 1，ceiling(-2) 返回 5，但 5 > 1 + 3 = 4，未命中；插入 1 得 {1, 5, 9}，删除 nums[1] = 5，集合 {1, 9}。i = 4，x = 5，ceiling(2) 返回 9，9 > 8，未命中；插入 5 得 {1, 5, 9}，删除 nums[2] = 9，集合 {1, 5}。i = 5，x = 9，ceiling(6) 在 {1, 5} 中无解，未命中。循环结束返回 false，与预期一致。

同一组输入走桶版本：桶宽 t + 1 = 4。i = 0，x = 1，桶号 0，三个桶都空，写入 {0: 1}。i = 1，x = 5，桶号 1，桶 1 空，桶 0 有值 1，5 - 1 = 4 > 3，桶 2 空，未命中，写入 {0: 1, 1: 5}。i = 2，x = 9，桶号 2，桶 2 空，桶 1 有值 5，9 - 5 = 4 > 3，桶 3 空，未命中，写入后删除 nums[0] = 1 所在的桶 0，得 {1: 5, 2: 9}。后续三步同理逐一落空，最终返回 false，两种实现结论一致。

代码实现

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

        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            Long ceil = set.ceiling(x - t);
            if (ceil != null && ceil <= x + t) {
                return true;
            }

            set.add(x);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }

        return false;
    }
}

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    if k <= 0 || t < 0 {
        return false
    }

    bucketSize := int64(t) + 1
    buckets := make(map[int64]int64)

    getBucket := func(x int64) int64 {
        if x >= 0 {
            return x / bucketSize
        }
        return (x+1)/bucketSize - 1
    }

    for i, v := range nums {
        x := int64(v)
        id := getBucket(x)

        if _, ok := buckets[id]; ok {
            return true
        }
        if val, ok := buckets[id-1]; ok && x-val <= int64(t) {
            return true
        }
        if val, ok := buckets[id+1]; ok && val-x <= int64(t) {
            return true
        }

        buckets[id] = x
        if i >= k {
            old := int64(nums[i-k])
            bid := getBucket(old)
            delete(buckets, bid)
        }
    }

    return false
}

复杂度分析

时间复杂度：有序集合版本为 $O(n \log k)$，凭据是每个元素恰好被插入一次、删除一次、发起一次范围查询，而集合中始终最多保留 $k$ 个元素，红黑树上这三种操作都是 $O(\log k)$；桶版本为 $O(n)$，凭据是每个元素只查固定的三个桶、做一次哈希写入和一次哈希删除，全是均摊常数操作。

空间复杂度：$O(\min(n, k))$，凭据是两种结构里存活的元素恰好是当前窗口内的元素，窗口长度不超过 k + 1，且元素总数不超过 n，与 t 的大小无关。

关键点总结

判据从「值相等」放宽到「值落在区间内」时，哈希表就失效了，必须换成支持有序查询的结构，或者把区间按判据宽度分桶，把范围查询编码成等值查询——这是这一类放宽题的通用应对。

范围查询只需检查「第一个不小于下界的候选」，因为它是所有合法候选中最小的，若它越界则其余必然越界。这条单调性论证可以直接复用到所有「有序结构上找区间内元素」的场景。

分桶时桶宽要取判据阈值加一，这样「同桶必合法」，而「合法但不同桶」的情况被限制在左右相邻的两个桶里，检查量从无界降为常数。

窗口的维护要点是「查询发生在插入之前、过期删除发生在本轮末尾」，这个顺序保证了任意时刻结构内容与不变量描述完全一致，是所有定长滑动窗口题的固定骨架。

值域跨满 int 时一切加减法都要先提升到 64 位，这不是防御性编程而是正确性要求，溢出会让边界判断整体反向。

面试视角：面试官最想听到的是你能说清「为什么哈希表不够用」，然后自然引出有序集合，并主动指出溢出风险。写完 $O(n \log k)$ 的版本后被追问能否做到线性，就把桶划分作为进阶方案抛出，并解释桶宽为什么取 t + 1、为什么只需看相邻桶。能把这两层讲完整，这题就答满了。

易错点总结

用 int 直接算 x - t：用例 nums = [-2147483648, 2147483647], k = 1, t = 2147483647，-2147483648 - 2147483647 溢出成正数，ceiling 找到的候选完全错位，会误返回 true。

先 set.add(x) 再做查询：用例 nums = [1, 2], k = 1, t = 0，第 0 位插入 1 后立刻 ceiling(1) 返回 1 自身，1 <= 1 成立，返回 true，而正确答案是 false。

过期删除的条件写成 i > k：用例 nums = [1, 2, 3, 1], k = 2, t = 0，处理 i = 3 时下标 0 的元素还留在集合里，1 与 1 配出差值 0，返回 true，而两者下标距离是 3，正确答案是 false。

忘记过期删除：用例 nums = [1, 100, 200, 1], k = 1, t = 0，集合一直累积，i = 3 时仍能找到下标 0 的 1，返回 true，正确答案是 false。

桶宽写成 t 而不是 t + 1：用例 t = 0，bucketSize 为 0，除法直接抛除零异常；即使 t = 3，桶宽 3 时值 2 和 5 差 3 合法却分属不同桶且相隔一格，需要多检查一个桶才不漏。

负数取桶号直接写 x / bucketSize：用例 nums = [-1, -4], k = 1, t = 2，桶宽 3，-1 / 3 在截断除法下得 0，-4 / 3 得 -1，两个差为 3 的数被分到相隔一格的桶，恰好漏判；必须用 (x + 1) / bucketSize - 1 做向下取整。

相邻桶命中就直接返回 true 而不验算差值：用例 nums = [1, 5], k = 1, t = 2，桶宽 3，1 在桶 0、5 在桶 1 相邻，但差值 4 大于 2，会误返回 true。

用 Set<Integer> 而不是 TreeSet 并逐个遍历窗口比较：用例 n = 20000, k = 19999 的全互异数组，退化成 $O(nk)$ 约 4×10^8 次比较而超时。

删除时用 set.remove(nums[i - k]) 而不做 (long) 转换：用例任意含重复值的数组，TreeSet<Long> 收到 Integer 参数比较失败，元素删不掉，窗口无限膨胀，nums = [1, 2, 3, 1], k = 1, t = 0 会误返回 true。

k 取 0 时不特判：用例 nums = [1, 1], k = 0, t = 0，若照常运行，i >= k 在第 0 轮就成立并去删下标 -k = 0 的元素，索引越界或逻辑错乱，正确做法是直接返回 false。

相似题目

题目	难度	考察点
219. 存在重复元素 II	简单	值条件收紧为完全相等，哈希表记最近下标即可，不需要有序结构
217. 存在重复元素	简单	连下标约束也去掉，退化成一次集合判重
1438. 绝对差不超过限制的最长连续子数组	中等	窗口长度不固定，要用单调队列维护极值并求最长长度而非存在性
239. 滑动窗口最大值	困难	定长窗口只取最值，用单调双端队列比有序集合更省
480. 滑动窗口中位数	困难	定长窗口要维护中位数，需要双堆配延迟删除或有序多重集