LeetCode LCR 057. 存在重复元素 III
题目描述
题意分析
寻找两个不同下标，使下标距离不超过
k，同时数值差的绝对值不超过t。一个条件约束位置，另一个条件约束值，必须同时满足。处理当前值
x = nums[i]时，只需查询前面至多k个元素中，是否存在落在[x-t, x+t]内的值。这样可以把下标条件交给滑动窗口，把数值条件交给窗口中的查询结构。
解法：滑动窗口（有序集合与分桶）
核心思路
[!blue]
查询下标
i时，容器保存的历史下标范围是[max(0, i-k), i-1]。先查询，再插入当前值；随后若i >= k，删除下标i-k的旧值，为下一轮准备窗口。这个旧值与当前下标相距恰好k，本轮仍然合法，所以必须在本轮查询之后才删除。Java 用有序集合回答数值查询。取
ceiling(x-t)，即不小于下界的最小值：若它存在且不超过x+t，就找到合法配对；若它已经超过上界，集合中更大的值也不可能符合要求。上下界在 64 位整数中计算，避免极端值的加减溢出。这里使用集合而非多重集合仍然正确：在题目
t >= 0的条件下，窗口内如果出现两个相等值，查询第二个时已经返回true。因此继续执行插入和删除的路径上，窗口里不会同时保留重复值，不会因为按值删除而误删其他副本。Go 把值域按宽度
size = t+1划成桶。每个桶包含连续的t+1个整数，同桶内两值的最大差为t，所以同桶已有元素时可以立即返回。相隔至少两个桶的值差必然大于t，其余只需检查左右相邻桶，并比较真实差值。桶号必须向下取整，让负数也按相同宽度分组。非负数直接除以
size；负数使用(value+1)/size-1，修正整数除法向零截断的行为。桶宽、桶号和差值都使用int64。同桶命中会直接结束搜索，所以每个桶只需保存一个值。两种实现都在插入前查询，保证当前元素不会和自己配对；容器只保留窗口范围，又保证了下标距离。
解题步骤
- 从左向右遍历，先在此前至多
k个元素中查找数值足够接近的候选。- Java 查询数值下界的后继；Go 检查当前桶和两个相邻桶，命中就返回
true。- 未命中时插入当前值，若
i >= k，再删除本轮使用完的nums[i-k]。- 全部元素处理完仍未命中则返回
false。k = 0时没有不同下标可选；t = 0时数值条件退化为完全相等。
代码实现
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
}
复杂度分析
设数组长度为
n，w = min(n, k+1)，包含插入当前值后、删除旧值前的短暂容量。
- 时间复杂度：Java 为 $O(n\log(w+1))$，每项进行常数次有序集合操作；Go 为期望 $O(n)$，每项只检查三个桶并做常数次哈希操作。
- 空间复杂度：$O(w)$，容器只保存当前窗口及刚插入的一项；每个桶至多保留一个值。
关键点总结
[!green]
- 窗口负责下标距离，范围查询或分桶负责数值距离。
- 下标
i-k本轮仍可参与配对，查完当前元素后才为下一轮移除。- 有序集合只需检查区间下界的最小后继；分桶只需检查同桶和相邻桶。
- 正确处理负数桶号和 64 位边界运算，是分桶判定成立的前提。
易错点总结
[!yellow]
- 先插入当前值再查询：会把当前元素当作自己的配对对象。
- 查询前就删除下标
i-k：会漏掉下标距离恰好等于k的合法配对。- 只查同桶：两个足够接近的值也可能跨过桶边界，必须检查相邻桶。
- 相邻桶命中就直接返回：相邻不代表差值一定足够小，仍需比较真实差值。
- 负数直接按向零截断计算桶号：会破坏桶的统一宽度，可能让差值过大的数误落在同桶。
- 先以 32 位计算上下界再转型：溢出可能已经发生，应先提升类型再运算。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 219. 存在重复元素 II | 简单 | 都限制下标距离，原题只查完全相同的值，本题允许值差，需要有序窗口或桶定位。 |
| 480. 滑动窗口中位数 | 困难 | 同样维护会插入和过期删除的窗口，原题查询中位数，本题查询邻近数值范围。 |