LeetCode LCR 057. 存在重复元素 III

2026-03-28 HGNULB 约 9 分钟

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

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 057. 存在重复元素 III

题意分析

题目目标：判断数组中是否存在两个下标 i 与 j，同时满足两个条件——下标之差不超过 k，且元素值之差的绝对值不超过 t，存在则返回真。
核心约束：这是一个"下标近 + 数值近"的双重邻近判定。下标条件天然对应一个宽度为 k 的移动区间，数值条件则要求在这个区间内查询"有没有值落在 $[x - t, x + t]$ 里"。两个条件一个管范围、一个管内容，解法必须同时覆盖。
边界处理：t 可以为 0，意味着要求值完全相等；元素值可以取到 32 位整型的两端，x + t 与 x - t 都可能溢出；k 可能大于数组长度，此时区间就是整个已遍历前缀；数组长度可达 $2 \times 10^4$，$O(nk)$ 在极端情况下不可接受。
实现取舍：因为只要判定存在性，一旦命中即可返回，无需统计数量；关键是找到一种能随区间移动而 $O(1)$ 或 $O(\log)$ 更新、并且支持范围查询的结构。

解法：滑动窗口维护区间

核心思路

暴力做法是对每个 i 往前看 k 个元素逐一比较，代价 $O(nk)$，在 k 接近 n 时退化成平方级。瓶颈很清楚：每次都把区间里的元素重新看一遍，但区间内容其实只在两端各变化一个元素。
于是把下标条件固化为不变量：处理下标 i 时，容器里恰好装着下标落在 $[i - k, i - 1]$ 内的所有元素。这一条靠"先查询、再插入当前元素、再删除下标为 i - k 的旧元素"三步维持。剩下的问题就变成——在这个容器里如何快速回答"是否存在值落在 $[x - t, x + t]$"。
第一种回答方式是把容器做成有序集合。有序性让"是否存在落在某区间内的值"这个查询退化成一次边界查找：取出不小于 $x - t$ 的最小元素，如果它存在且不超过 $x + t$，说明区间内有值，返回真；如果它都已经超过 $x + t$，那么比它更大的更不可能落进来，直接判否。单次查询与增删都是 $O(\log k)$。
第二种回答方式是分桶。把整个值域按宽度 t + 1 切成一个个桶，同一个桶内任意两数之差必然不超过 t，所以只要当前元素要进的桶已经有人，立刻返回真；差值不超过 t 的另一种可能只会出现在左右相邻的两个桶里，各检查一次即可，更远的桶差值必然大于 t。因为同桶命中会立即返回，所以每个桶至多存一个元素。桶宽取 t + 1 而不是 t，是为了让"同桶必然合法"成立；负数除法要单独处理，否则 -1 与 1 会被错误地归进同一个桶。
两种方式共享同一条窗口不变量，区别只在于回答范围查询的手段：有序集合是 $O(\log k)$ 但通用，分桶是 $O(1)$ 但依赖值域可以均匀切分。

解题步骤

遍历下标 i，在做任何插入之前先完成查询。为什么顺序不能反：容器代表的是"当前元素之前的窗口"，若先把自己插进去，t 为 0 时会查到自己，把一个元素当成两个用。

有序集合写法里取 ceiling(x - t)，即不小于 x - t 的最小元素。为什么取这一个就够：它是所有大于等于下界的候选中最小的，若连它都超过了上界 x + t，则不存在任何落在区间内的值；若它没超过，区间内就有值。

所有参与运算的量都提升为 64 位。为什么必须提升：x 可能接近 $2^{31} - 1$ 而 t 又是正数，x + t 在 32 位下会溢出成负数，导致判定完全错乱。

插入当前元素后，若 i >= k 则删除下标为 i - k 的元素。为什么删除条件是 i >= k：窗口要保留的是最近 k 个下标，当 i 达到 k 时，下标 i - k 已经超出了"下标之差不超过 k"的范围，必须移出。

分桶写法里先算当前值的桶号，桶号已存在就直接返回真。为什么可以不比较具体数值：桶宽是 t + 1，同桶内两数之差至多为 t，必然满足条件。

再检查左右相邻桶，命中时还要显式比较差值是否不超过 t。为什么这里必须比较：相邻桶的两个数可能分处两端，差值最大可到 2t + 1，不一定合法。

负数的桶号用 (value + 1) / size - 1 计算。为什么不能直接整除：多数语言的整数除法向零截断，-1 / 2 与 1 / 2 都得 0，会让 -1 和 1 同桶，t 为 1 时误判为真。

以 具体用例：nums = [1, 5, 9, 1, 5, 9]，k = 2，t = 3 走一遍有序集合写法。i = 0，容器空，查询失败，插入 1。i = 1，x = 5，取不小于 2 的最小元素——容器 {1} 中没有，查询失败，插入 5。i = 2，x = 9，取不小于 6 的最小元素，容器 {1, 5} 中没有，失败；插入 9 后 i >= k 成立，删除下标 0 的元素 1，容器变 {5, 9}。i = 3，x = 1，取不小于 -2 的最小元素得 5，但 5 > 1 + 3 = 4，失败；插入 1 并删除下标 1 的元素 5，容器变 {1, 9}。i = 4，x = 5，取不小于 2 的最小元素得 9，9 > 8，失败；插入 5，删除下标 2 的元素 9，容器变 {1, 5}。i = 5，x = 9，取不小于 6 的最小元素得 9？容器里只有 {1, 5}，没有不小于 6 的元素，失败。遍历结束返回假，与逐对枚举核对一致。再看一个正例，nums = [1, 2]，k = 1，t = 1：i = 1 时查不小于 1 的最小元素得 1，且 1 <= 3，立即返回真。

代码实现

// 核心实现：滑动窗口维护区间，维护必要状态并避免重复处理。
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> ts = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            Long x = ts.ceiling((long) nums[i] - (long) t);
            if (x != null && x <= (long) nums[i] + (long) t) {
                return true;
            }
            ts.add((long) nums[i]);
            if (i >= k) {
                ts.remove((long) nums[i - k]);
            }
        }
        return false;
    }
}

// 核心实现：滑动窗口维护区间，维护必要状态并避免重复处理。
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    if k <= 0 || t < 0 {
        return false
    }
    size := int64(t) + 1
    buckets := map[int64]int64{}
    for i, num := range nums {
        value := int64(num)
        id := bucketID(value, size)
        if _, ok := buckets[id]; ok {
            return true
        }
        if v, ok := buckets[id-1]; ok && value-v <= int64(t) {
            return true
        }
        if v, ok := buckets[id+1]; ok && v-value <= int64(t) {
            return true
        }
        buckets[id] = value
        if i >= k {
            delete(buckets, bucketID(int64(nums[i-k]), size))
        }
    }
    return false
}

func bucketID(value int64, size int64) int64 {
    if value >= 0 {
        return value / size
    }
    return (value+1)/size - 1
}

复杂度分析

时间复杂度：有序集合写法 $O(n \log \min(n, k))$，分桶写法 $O(n)$。凭什么：前者每个元素做常数次插入、删除与边界查找，集合规模不超过 k；后者每个元素只算一次桶号并检查三个桶，全部是哈希常数操作。

空间复杂度：均为 $O(\min(n, k))$。凭什么：两种结构都只保存窗口内的元素，窗口宽度上限是 k，而分桶因为同桶即返回真所以每桶至多存一个数。

关键点总结

双重邻近条件的通用拆法是"一个条件管窗口范围、另一个条件管窗口内查询"，先把窗口不变量钉死，再单独设计查询结构，思路就不会纠缠在一起。

有序集合把"区间内是否有值"压成一次边界查找，是范围存在性查询的标准手段；只取不小于下界的最小元素这一步，蕴含了"更大的更不可能"的单调性论证。

分桶的桶宽必须取 t + 1，才能保证"同桶必合法"；也正因如此只需再看左右各一个相邻桶，这是把 $O(\log k)$ 降到 $O(1)$ 的关键。

负数除法向零截断会破坏桶的均匀划分，凡是值域含负数的分桶题都要单独处理这一支，否则错误只在负数用例上暴露。

面试视角：这题是典型的"两种解法各有卖点"。面试时先给有序集合版本（好写、好证），再主动提出桶优化并说明桶宽为什么是 t + 1；同时一定要点出溢出风险并说明用 64 位或用差值比较来规避——这三点齐了就是满分答案。

易错点总结

错误写法：用 int 计算 nums[i] + t → 输入 nums = [2147483647, -2147483647]、k = 1、t = 2147483647 时上界溢出成负数，判定反转，返回错误结果。

错误写法：先把当前元素插入容器再查询 → t = 0 时元素与自己相等，任何非空数组都返回真，例如 [1, 2]、k = 1、t = 0 应返回假却返回真。

错误写法：删除条件写成 i > k → 窗口比要求宽一位，nums = [1, 0, 1]、k = 1、t = 0 中下标 0 与 2 被当成合法配对，返回真而正确答案是假。

错误写法：删除时用 nums[i] 而不是 nums[i - k] → 刚插入的元素立刻被删掉，容器始终为空，任何输入都返回假。

错误写法：桶宽取 t 而不是 t + 1 → t = 0 时除以 0 直接崩溃；t = 1 时同桶两数之差可能为 1 之外还可能不合法，判定失去依据。

错误写法：分桶时不处理负数，直接 value / size → nums = [-1, 1]、k = 1、t = 1 中两数被分进同一个桶（都算作桶 0），返回真而正确答案在 t = 1 下确实是真，但换成 t = 0 时同样同桶却会误判为真。

错误写法：只检查同桶不检查相邻桶 → nums = [1, 2]、k = 1、t = 1 中 1 与 2 分处桶 0 与桶 1，被漏判，返回假。

错误写法：检查相邻桶时不比较实际差值 → nums = [1, 4]、k = 1、t = 2 中两数分属相邻桶但差值为 3，误判为真。

错误写法：有序集合里用 floor(x + t) 却仍与下界比较方向写反 → 判定条件与查询方向不匹配，nums = [1, 5]、k = 1、t = 1 这类反例会给出错误结论。

错误写法：用普通哈希集合代替有序集合再遍历集合找区间 → 语义正确但每次查询 $O(k)$，整体退回 $O(nk)$，k 接近 $2 \times 10^4$ 时超时。

相似题目

题目	难度	考察点
217. 存在重复元素	简单	只有数值相等条件，无窗口限制，一张集合即可
219. 存在重复元素 II	简单	加上下标距离限制但值必须完全相等，无需范围查询
1438. 绝对差不超过限制的最长连续子数组	中等	窗口宽度不固定，需用单调队列同时维护最大最小值
239. 滑动窗口最大值	困难	定宽窗口求极值，单调队列比有序集合更快
480. 滑动窗口中位数	困难	定宽窗口求中位数，需要对顶堆或有序结构支持删除
LCR 041. 数据流中的移动平均值	简单	同样是定宽窗口，但统计量可增量加减无需查询结构