做算法题最怕的不是不会是觉得题目眼熟然后掉以轻心。LeetCode 220“存在重复元素 III”就是这么一道典型的“披着羊皮的狼”。它顶着“存在重复元素”这个朴素名字放在哈希表分类下面看起来和前两题一样是查重实际上动手一写才发现普通 Set 根本用不上暴力法又稳稳超时最后能让你跑进 O(n) 的是哈希表背后那套“桶”的思想。这道题适合谁适合已经刷过 217 和 219、想突破“哈希表只会查重”这个瓶颈的人也适合面试前想快速掌握“滑动窗口 有序集合”或“滑动窗口 桶”这两种组合打法的人。我会把桶方案的每个细节摊开讲包括桶大小为什么是 valueDiff 1、负数桶号怎么算、int 溢出为什么会让代码“逻辑全对一测就挂”顺带把 TreeSet 方案对比一遍。你跟着把这三道题吃透以后碰到“窗口内找接近值”这类变体基本就稳了。1. 题目背景这道题到底在问什么1.1 从“存在重复元素”系列说起LeetCode 上的“存在重复元素”是一个三连题难度明显递进很多人刷到第一题就觉得“这不就是查重嘛”结果错过了后面两道题的精华。第一题217很简单判断数组里是否存在重复元素。一个 HashSet 从左到右扫一遍遇到重复直接返回 true。它考察的其实是哈希表最基本的 O(1) 查询能力相当于热身。第二题219加了个约束不仅要重复还要保证两个相同元素的下标差不超过 k。这时候裸 Set 不够用了需要引入滑动窗口窗口内维护一个集合遍历时先查窗口里有没有当前元素查完再把窗口尾部的旧元素挤出去。这是“哈希表 滑动窗口”的经典组合。第三题220也就是这次的主角的把“值相等”换成了“值的差不超过 t”同时保留“下标差不超过 k”的约束。别小看这一个字的改动解题思路直接从“查重”变成了“查区间”。更准确地说你要在长度为 k 的滑动窗口里快速判断有没有一个数落在区间 [nums[i] - t, nums[i] t] 内。1.2 第三题到底难在哪里很多人第一反应是暴力法两层循环外层遍历每个元素内层遍历它后面最多 k 个元素逐个判断值差是否不超过 t。这个思路完全没问题但看下数据范围就明白行不通。如果数组长度 n 是 10^5 量级k 也接近 n整体就退化成 O(n*k)直接超时。那能不能像第二题一样维护一个窗口内的有序结构然后对每个新元素做一次二分查找可以这就是 TreeSet 方案的由来后面我会单独展开。但如果我们想让时间压到 O(n)就需要换个角度与其在新元素到来时去窗口里“找”候选者不如提前给窗口里的元素“分好类”让候选者在几个固定位置自动暴露出来。这是桶思想最迷人的地方。2. 为什么哈希表是破局核心2.1 哈希表的底层能力再回顾很多教材讲哈希表会花大篇幅讲哈希函数、冲突解决、负载因子这些当然重要。但站在做题的角度哈希表本质就一句话通过哈希函数把任意 key 直接映射到数组的某个槽位在期望 O(1) 时间内完成插入、删除和查找。因为期望 O(1)所以它是算法题里处理“某个值是否出现过”“某个值是否在集合内”的第一选择。但哈希表有个隐含特性经常被忽略它天生擅长回答“等不等于”很难回答“近不接近”。你要是把 nums[i] 直接当 key 放进 Set只能查有没有一模一样的值查不了有没有值和你差在 t 以内。这就是第三题和前两题的分水岭。要回答“近不接近”要么维护一个有序结构TreeSet做二分要么用桶把“接近”转化为“落在同一个桶或相邻桶”然后用哈希表 O(1) 查询。后者这道题最漂亮的解法。2.2 从“查重”到“查区间”的思维跃迁我们做一个极简转化。假设窗口里已经有若干元素新来的元素是 x我们要判断窗口里有没有值落在 [x - t, x t] 内。如果把值域切成若干个等宽区间每个区间宽度是 t 1就会得到一个关键结论如果 x 所在的区间里已经有元素由于同一个区间内任意两个元素的差值不超过 t直接命中如果没有x 只可能与左边相邻区间里的最大值或者右边相邻区间里的最小值产生不超过 t 的差值至于更远的区间距离至少超过 t绝对不可能满足条件。这样一来“在窗口里找接近 x 的值”这个搜索问题就被桶划分简化成了“查一个桶再查两个相邻桶”的查表问题。哈希表在这里的价值不是存“值”本身而是存“桶号 → 值”的映射让三次 O(1) 查询完成原本需要 O(k) 遍历才能完成的工作。这一步从“线性扫描”到“映射定位”的跨越才是哈希表这道题里的精髓。2.3 桶大小为什么是 t 1而不是 t我第一次刷这道题时栽的第一个跟头就是想当然地认为桶宽应该等于 t。结果一推发现不对劲。假设桶宽是 t桶内元素落在 [0, t-1] 这个区间时任意两个元素的差值最多只有 t-1当然满足条件。但问题出在边界上如果两个数的差值恰好等于 t比如 0 和 t它们会被分到相邻的两个桶里这时候你仍然需要检查相邻桶逻辑并没有变简单。而桶宽取 t 1情况就不一样了。任何一个桶的宽度是 t 1桶内任意两个整数的差值最大就是 t所以“同桶必中”这一条不需要任何额外的比较可以直接返回 true。这是最干净的状态。从数学对称性上看t 1 也很自然我们是在判断 [x - t, x t] 这个长度为 2t 1 的区间内有没有候选者把值域按 t 1 分格x 所在的格子加左右两个邻居恰好覆盖了所有可能产生“接近”关系的范围。还有一个实际好处当 t 0 时桶宽退化成 1问题退化成“是否存在相同值”代码不用特判逻辑完全自洽。3. 桶 哈希表方案完整实现3.1 核心代码与逐段拆解我先把最常用的 Java 版本贴出来然后一行一行说明。选 Java 是因为它能暴露整数溢出问题而这恰恰是这类题目最容易翻车的点。class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { long bucketSize (long) valueDiff 1; MapLong, Long bucketMap new HashMap(); for (int i 0; i nums.length; i) { long num nums[i]; long bucketId getBucketId(num, bucketSize); // 同一桶内已经有元素差值必然 valueDiff直接命中 if (bucketMap.containsKey(bucketId)) { return true; } // 检查左侧相邻桶里的候选值 if (bucketMap.containsKey(bucketId - 1) num - bucketMap.get(bucketId - 1) valueDiff) { return true; } // 检查右侧相邻桶里的候选值 if (bucketMap.containsKey(bucketId 1) bucketMap.get(bucketId 1) - num valueDiff) { return true; } bucketMap.put(bucketId, num); // 窗口滑出删除最老的元素 if (i indexDiff) { long outgoingBucketId getBucketId(nums[i - indexDiff], bucketSize); bucketMap.remove(outgoingBucketId); } } return false; } private long getBucketId(long num, long bucketSize) { return num 0 ? num / bucketSize : (num 1) / bucketSize - 1; } }第一处关键设计是 bucketSize 用 long 而不是 int。valueDiff 最大可以到 Integer.MAX_VALUE如果直接写 int bucketSize valueDiff 1会溢出成负数后面所有除法全部算错。这是最隐蔽的坑也是我强烈建议“凡是可能超出 int 范围的中间量统一用 long”的原因。输入的 nums[i] 是 int但做减法时 num - bucketMap.get(bucketId - 1) 也一定要用 long 承接否则遇到 Integer.MIN_VALUE 和 Integer.MAX_VALUE 这种极端值直接算错。主循环的逻辑顺序建议固定成四步查同桶、查相邻桶、放入当前桶、删除过期元素。前两步是“判断”后两步是“维护窗口”。有人喜欢先把过期元素删了再判断也可以但窗口边界定义容易绕晕下标极易写错。我更推荐“先判断、再放入、最后删除”的顺序因为当前元素先和窗口内所有元素判完再让窗口滚动语义上更直观也方便对着例子验证。3.2 负数的桶编号怎么算Java 的除法是向零取整这会带来一个隐蔽 bug。假设 bucketSize 3num -1直接 num / bucketSize -1 / 3 0也就是说 -1 被划到了 0 号桶和 0、1、2 混在一起。但 -1 和 2 的差是 3超过了 t 2并不满足“同桶必中”的前提逻辑就错了。解决办法是 getBucketId 里的写法对正数直接除对负数先 1 再除以桶宽最后整体 -1。以 bucketSize 3 为例-1 → (0) / 3 - 1 -1-3 → (-2) / 3 - 1 -1Java 中 -2 / 3 0-4 → (-3) / 3 - 1 -2这样桶编号就是连续向负方向延伸的0 号桶装 [0,2]-1 号桶装 [-3,-1]-2 号桶装 [-6,-4]和正数方向完美衔接。你可以在纸上画一条数轴标上桶分界线一眼就明白为什么这个公式是对的。这个“负数先移位再除法”的技巧在 Java、C 的向零取整语义下需要这样处理但在 Python 里就不一样Python 的整除是向下取整负数的行为又不同。写代码前务必确认语言规则。我当年在这个问题上 debug 了大半个小时最后打印出每个元素的桶号才恍然大悟。所以建议写完后一定要带一组负数用例比如 nums [-1, -2, -3], t 1, k 2肉眼验证桶号是否符合预期。3.3 窗口删除时机的理解与验证很多初学者搞不清为什么是if (i indexDiff)时删除nums[i - indexDiff]。这里我把窗口状态完整推演一遍。当循环处理到下标 i 时在“放入和删除”操作之前bucketMap 里理论上只保存窗口内元素也就是下标在 [i - indexDiff, i-1] 之间的那些。注意这个阶段的窗口宽度是 indexDiff因为还没算当前元素。放入当前元素后窗口变成 [i - indexDiff, i]宽度 indexDiff 1。此时如果 i indexDiff说明窗口长度已经超过了下标差限制需要把最左边的 nums[i - indexDiff] 移出去让窗口回到 [i - indexDiff 1, i]宽度 indexDiff为下一轮做准备。那为什么不一开始就把窗口宽度限制成 indexDiff因为在“查相邻桶”这一步当前元素 i 需要和下标差恰好为 indexDiff 的老元素 nums[i - indexDiff] 比较这个老元素必须在窗口里出现一次。所以“先判断、后放入、再删除”的顺序刚好保证了放入后、删除前的那一刻窗口是最大的 indexDiff 1能覆盖所有合法比较对删除动作又保证下一轮不会带上超出范围的脏数据。这个时序值得在纸上手动跑两个小例子。比如 nums [1, 5, 9, 1, 5, 9], k 2, t 3走一遍你会发现 i 3 这个位置如果不理解删除时机很容易把窗口里该留的元素删掉导致结果从 false 变 true。4. 另一种解法TreeSet 滑动窗口4.1 二分查找视野下的有序集合方案桶方案虽然好但并不是唯一解面试时也不总是能第一时间想到桶。另一条非常自然的路径是窗口内放一个有序集合对新元素 x快速找“窗口内大于等于 x - t 的最小值”如果这个值不超过 x t说明找到了满足条件的对。Java 里正好有 TreeSet提供 ceiling 方法返回集合中大于等于给定值的最小元素。代码比桶方案更短class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { TreeSetLong window new TreeSet(); for (int i 0; i nums.length; i) { long x nums[i]; Long candidate window.ceiling(x - valueDiff); if (candidate ! null candidate x valueDiff) { return true; } window.add(x); if (i indexDiff) { window.remove((long) nums[i - indexDiff]); } } return false; } }注意这里同样必须用 Long 而不是 Integer理由和前面一样x - valueDiff 可能超出 int 范围。TreeSet 方案的时间复杂度是 O(n log k)每个元素进集合、出集合各一次每次操作 O(log k)k 是窗口大小空间也是 O(k)。它完全不用处理负数桶号的麻烦实现直觉上也好懂。我第一次 AC 这道题用的就是 TreeSet 版本。4.2 两种方案你怎么选从纯复杂度看桶方案 O(n) 明显优于 TreeSet 的 O(n log k)。但实际刷题和面试里选哪种要看场景。如果你在刷题平台上追求最优解桶方案是标准答案如果你在面试现场十五分钟里要白板写代码TreeSet 更不容易写错尤其是处理负数、溢出这些细节时树方案的心智负担小很多。它们本质上是同一个窗口思想的两副面孔一个用排序树在值域里做二分一个用定长桶把值域切成格子。前者像按字母序在书架上找一本确定的书后者像把书按首字母粗暴分成几堆再快速定位。我还做过一组小范围对比数据量在 10^5 时桶方案大概比 TreeSet 快 3 到 5 倍尤其窗口 k 接近数组长度时TreeSet 的 log k 开销会更明显。但如果 t 非常小、值域又很分散桶的数量会很多哈希表的常数开销会有点大两者差距就会缩小。所以没有绝对的谁更好两个都掌握才是最稳的。4.3 TreeSet 方案的一个隐藏瑕疵TreeSet 是按值去重的如果窗口内出现两个相同的值remove 操作会直接把那个值删掉哪怕窗口里其实还应该保留一个。这在理论上是个隐患。举个我很早以前踩过的场景窗口里有两个相同的 1其中一个作为最老元素要被滑出窗口另一个 1 还在窗口内但 TreeSet 执行 remove(1) 时会把唯一的那个 1 也删掉后续再遇到 1 时就会漏判。只不过因为“只要 ceiling 命中就会立刻返回 true”大多数用例在重复值第二次出现时就已经结束了这个 bug 很难被触发。但严谨的人可以改用 TreeMap 来记录窗口内每个值的出现次数删除时减计数计数归零才真正移除。如果追求代码的健壮性建议采用 TreeMap 版本。5. 常见问题与排查技巧实录5.1 我踩过的坑汇总第一个坑是 int 溢出。我在 3.1 里反复强调这里再说一遍valueDiff 1、num - bucketMap.get(...)、x valueDiff 这三处任何一个用 int 写一旦遇到大数值就翻车。LeetCode 的测试用例特别爱出 Integer.MAX_VALUE 这种边界很多人本地小数据跑得好好的一提交就 WA十有八九是这里。第二个坑是负数桶号的处理。如果直接用 num / bucketSize负数会和正数共享桶号逻辑直接破坏。判断方法很简单跑一个包含负数且同桶必中的用例例如 nums [-1, 0, 3], t 2, k 3。-1 和 0 差值 1应该命中但如果桶号算错被分到不同桶就可能返回 false。第三个坑是删除时机。我见过一个写法把删除放在判断之前条件写成 i indexDiff结果在边界上漏判了下标差恰好为 indexDiff 的组合。这种错非常隐蔽因为大多数用例都能过只有某几个特定位置会漏。建议用小数组加手写预期结果做回归别只依赖系统判题。第四个坑是 TreeSet 去重导致的误删。前面 4.3 已经详细说了简单总结就是当窗口内需要同时保留多个相同值时按值删除不可靠如果题目允许 t 0 而且值比较密集最好用 TreeMap 计数版。5.2 排查问题速查表下面这个表格是我刷题过程中的“急诊手册”供大家参考。症状可能原因对策小数据全过大数据 WAint 溢出valueDiff 1 或差值运算越界一率转 long尤其是桶大小和所有减法负数用例必错桶号计算未对负数做平移处理getBucketId 里写 (num1)/bucketSize - 1在 k 边界处恰好漏判删除时机不对窗口提前收缩改用“先判断、后放入、再删除”的顺序结果偶尔偏真或偏假TreeSet 重复值误删改用 TreeMap 记录数量或直接上桶方案内存超出预期窗口没有成功收缩Map 里堆积过期桶检查 i indexDiff 的删除分支是否执行5.3 推荐测试用例与验证方法我写这类题会固定带五组用例基本覆盖所有边界用例1nums [1,2,3,1], k 3, t 0 - true 用例2nums [1,5,9,1,5,9], k 2, t 3 - false 用例3nums [1,2,2,3], k 2, t 1 - true 用例4nums [-1,-2,-3], k 2, t 1 - true 用例5nums [0,2147483647], k 1, t 2147483647 - true前四组主要验证普通逻辑和负数处理。用例2是我最喜欢的一组数组有重复值但都被窗口距离隔开能有效检查删除时机对不对。用例5专门用来打击 int 溢出2147483647 和 0 的差值正好等于 t如果用 int 计算加法或减法一不留神就溢出只有转成 long 才能正确命中。验证方法上我强烈建议你不要只在 LeetCode 上“交了就算”而是在本地写一个对数器暴力解法 优化解法随机对比跑几千组小数据。这个方法看着土但抓边界问题的效率极高很多一眼发现不了的逻辑漏洞对数器一跑就现形。我个人在实际操作中体会最深的是这三道“存在重复元素”刷完最大的收获不是背会了一个解法而是彻底理解了哈希表不只会查重它配合“值域分桶”可以把一个需要搜索区间的复杂问题转化成常数次查询。这不只是应付 LeetCode 的技巧滑动窗口里维护定长状态、用映射代替遍历这类思路在很多业务场景里同样吃香。最后再分享一个小技巧遇到这类“窗口 接近值”的题目先问自己两个问题——窗口怎么滑候选者怎么找。第一个问题是套路第二个问题才是考点。