LeetCode 220. 存在重复元素 III
题目描述
题意分析
判断是否存在两个不同位置，下标差不超过
indexDiff，数值差不超过valueDiff。下文和代码分别用k、t表示这两个限制：按原下标顺序维护最近k个位置，再在这些候选中判断值差。
解法一：滑动窗口 + 有序集合
核心思路
[!blue]
处理下标
i前，只保留下标区间[max(0, i-k), i)中的值。它们都与当前位置不同，并且下标差不超过k；因此剩下的问题是：有序集合中是否存在一个值落在[x-t, x+t]，其中x = nums[i]。
set.ceiling(x-t)返回不小于下界的最小值。若不存在，所有候选都小于下界；若它大于x+t，其他不小于下界的值只会更大。只有它位于上界以内时才存在答案，所以每轮只检查这一个候选即可。必须先查询，再插入
x，避免把当前位置与自己配对。本轮检查结束后，若i >= k，删除下标i-k对应的旧值：它与当前下标相差k，本轮仍可使用，但与下一下标相差k+1，必须在下一轮前移除。普通集合不保存重复次数也足够：只要有效窗口中出现两个相同值，值差为 0，就已经返回
true。因此执行到插入、删除时，窗口内不会有重复值，删除过期值不会误删另一个仍有效的副本。代码用long保存值并计算上下界，删除时也使用相同类型。
解题步骤
- 将值提升为宽整数。
- 查询下界的最小后继并比较上界。
- 未命中才加入当前值。
- 本轮末尾移除下标
i-k，为下轮维持有效窗口。- 全部位置都未命中时，返回
false。
代码实现
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k <= 0 || t < 0) {
return false;
}
TreeSet<Long> set = new TreeSet<>();
// 查询时只保存此前至多 k 个位置，不包含当前下标
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);
// 本轮末尾删除 i 减 k 的旧位置，为下一轮维护窗口
if (i >= k) {
set.remove((long) nums[i - k]);
}
}
return false;
}
}
复杂度分析
- 时间复杂度：$O(n\log(\min(n,k)+1))$，
n为数组长度，每项执行常数次有序集合操作。- 空间复杂度：$O(\min(n,k)+1)$，含插入后暂时多出的一项。
关键点总结
[!green]
- 查找范围的最小候选即可，无需扫描整个集合。
- 位置窗口按原顺序维护，不能排序输入。
- Java 集合保存宽整数，删除旧值也使用相同类型。
解法二：滑动窗口 + 分桶
核心思路
[!blue]
沿用相同的下标窗口，把其中的值按宽度
w = t+1分桶。桶号为b的桶覆盖整数[b*w, (b+1)*w-1]，桶内最大差是w-1 = t，所以当前值的桶中只要已有元素，就可以直接返回true。若两个桶的编号至少相差 2，即使取最近的两个端点，差也至少为
w+1，已经超过t。因此只需再检查左右相邻桶；邻桶中的值可能接近，也可能相差很远，必须验证实际差值。左桶中的值小于当前值，右桶中的值大于当前值，所以两侧分别使用x-val与val-x。桶号必须是
floor(x/w)。Go 的整数除法对负数向零截断，所以x < 0时用(x+1)/w-1得到向下取整的结果，避免把零两侧的数错误地放入同一个过宽的桶。宽度、桶号和值都使用int64计算。每轮先检查三个桶，未找到答案才把当前值写入本桶，再删除下一轮过期位置所属的桶。同桶出现两个有效元素时早已返回成功，因此继续执行时每个桶最多只有一个值，删除整个过期桶不会丢失其他有效候选。
解题步骤
- 桶宽使用宽整数计算
t+1。- 计算当前值桶号，负数补偿向零截断的除法。
- 检查同桶与相邻桶，相邻时再验证差值。
- 写入当前值，并删除下一轮过期位置所属桶。
- 扫描结束仍无匹配则返回
false；t = 0时桶宽为 1，只会接受相等的数。
代码实现
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
}
// 查询时只保存此前至多 k 个位置，不包含当前下标
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
// 本轮末尾删除 i 减 k 的旧位置，为下一轮维护窗口
if i >= k {
old := int64(nums[i-k])
bid := getBucket(old)
delete(buckets, bid)
}
}
return false
}
复杂度分析
- 时间复杂度：期望 $O(n)$，每项最多检查三个哈希桶。
- 空间复杂度：$O(\min(n,k)+1)$，只保存有效窗口桶。
关键点总结
[!green]
- 桶宽含端点差，因此取阈值加一。
- 负数必须使用向下取整的桶号。
- 邻桶仅表示可能接近，仍需实际差值检查。
易错点总结
[!yellow]
- 先插入再查询，会把当前元素与自己配对。
- 过期位置未删除，会接受下标距离超限的值。
- 邻桶存在就直接成功，会把实际差值过大的配对误计。
- 负数桶号向零截断，会扩大零附近的桶范围，误收本不接近的值。
- Java 有序集合存放宽整数，边界运算和删除旧值都要使用相同类型。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 219. 存在重复元素 II | 简单 | 都限制下标距离，原题只查完全相同的值，本题允许值差，需要有序窗口或桶定位。 |
| 480. 滑动窗口中位数 | 困难 | 同样维护会插入和过期删除的窗口，原题查询中位数，本题查询邻近数值范围。 |
| 217. 存在重复元素 | 简单 | 重复元素系列。去掉距离限制并要求两个值相同后，可简化为集合判重。 |