刷 LeetCode 刷到一定量之后你会慢慢发现一个很有意思的现象凡是跟“重复元素”沾边的题不管它挂在哪个标签下面底层解法就那么几板斧——哈希表、排序、双指针、位运算、龟兔赛跑。这周我集中过了一遍 LeetCode 100 Hot 里的相关题目从“存在重复元素”到“寻找重复数”难度从简单一路到偏难但解法模型高度统一。这篇文章就把这些题串起来讲重点不是我贴几份能提交的代码而是帮你建立一个“看到重复元素就知道往哪个方向想”的解题框架。适合谁看一是刚开始刷题、被 217、26、83 这种简单题搞蒙的新手二是刷到中等题想总结套路、准备面试手撕代码的人。文里会涉及数组、链表、哈希表、位运算这些基础数据结构但不会讲太高深的理论所有内容都可以直接在你的编辑器里跑起来验证。1. 重复元素题型的核心脉络一个主题五种解法模型1.1 为什么“重复元素”值得专门写一篇总结你仔细观察 LeetCode 的题单会发现“重复元素”不是某个特定标签下的题目而是横跨数组、链表、哈希表、排序、位运算、二分查找多个分类的题型。这种分散性恰恰是它值得系统总结的原因面试官想考察的往往不是某一个孤立知识点而是你能不能把一个数据结构问题抽象成若干种通用解法。从题目本身看重复元素问题有一个非常明显的特征——几乎所有题目都围绕着“唯一性”做文章。有的题只问“是否存在重复”有的题要求“把重复的删掉”有的题要求“找出那个重复的”还有的题更进一步限定“最多保留 k 个”。这些问题从表面看差异巨大但底层考察的都是同一个能力你能不能高效判断和处理集合中元素的唯一性。我刷完这一批题后最大的感受是重复元素题真正想训练的是两件事第一理解哈希表是解决唯一性问题的第一直觉第二在空间受限或数据有序的特殊条件下怎么用更巧的解法替代哈希表。这两点贯穿了所有重复元素题目也是面试官层层加码考察的核心。1.2 五种解法模型和它们的分工我把重复元素相关题目归纳为六种解法它们在时间复杂度和空间复杂度上有明显差异适用场景也不同。先给你一张速览表后面逐一展开解法模型典型题目时间复杂度空间复杂度核心适用条件哈希表/哈希集合217、219O(n)O(n)最通用最简单的保底方案排序后扫描217 的解法二O(n log n)O(1)可以修改原数组不要求保序双指针26、80O(n)O(1)数组已有序需要原地修改链表哑节点 值比较83、82O(n)O(1)排序链表场景位运算异或136O(n)O(1)恰好存在一个出现奇数次的元素正负号标记442、448O(n)O(1)数组元素范围是 1 到 n龟兔赛跑 / 二分计数287O(n) / O(n log n)O(1)不能修改数组且数值范围明确这张表你可以打印出来贴在显示器边上。实际刷题时看到题目先往表里套大概率能快速锁定方向。接下来我会按常见程度逐个讲清楚其中双指针和链表是面试手撕代码的高频考法篇幅会多一些。2. 数组去重双指针是面试官真正想看的答案2.1 第 26 题“删除有序数组中的重复项”快慢指针的完整拆解这道题是 LeetCode 的简单题也是面试中出现频率极高的一道。题目描述很直接给你一个升序排列的数组要求原地删除重复元素让每个元素只出现一次返回删除后数组的新长度。注意两个约束原地和升序——这基本就是在提示你双指针解法。先想一个问题为什么不能用简单的“遍历 删除”来做因为数组的删除操作是 O(n) 的你每删一个元素后面的所有元素都要往前挪最坏情况下整体复杂度会退化到 O(n²)。而且题目要求“原地”意味着你不能新建一个数组再拷贝回去。双指针的思路其实很生活化想象你手里有两个人一个慢指针 slow 负责在数组前面“圈地”一个快指针 fast 负责在前面探路。slow 记录的是“下一个不重复元素应该放到的位置”fast 则从头到尾扫描整个数组。因为数组有序相同的元素一定连续排列所以只要发现 fast 指向的元素和 slow 位置的元素不同就说明遇到了一个新的不重复元素把它挪到 slow 位置然后 slow 前进一位。def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1注意几个容易出错的地方。第一slow 从 0 开始因为第一个元素无论如何都会保留第二比较的是nums[fast]和nums[slow]而不是nums[fast]和nums[fast - 1]——虽然这两种写法在有序数组上结果一样但前者更好推广到“最多保留 k 个重复项”的通用场景第三返回值是slow 1因为 slow 是最后一个不重复元素的下标长度是下标加一。我第一次写这道题的时候在返回长度上栽过跟头——如果 slow 初始化为 1返回的就是 slow如果初始化为 0返回的就是 slow 1。这个细节看起来不起眼但在面试手撕代码时很容易因为紧张在边界上翻车。建议你固定一种写法比如都从 0 开始最后返回 slow 1这样就只需要记一种模式。2.2 第 80 题“删除有序数组中的重复项 II”从“留一个”到“留 K 个”的通用模板第 80 题是 26 题的升级版这次要求每个元素最多出现两次而不是一次。如果你已经理解 26 题的快慢指针这题其实只改一个条件但很多人就是卡在这个“差一点”上。26 题比较的是nums[fast]和nums[slow]因为 slow 指向的是最后一个保留元素新元素和它不同就说明是最多出现一次。到了 80 题我们需要知道当前元素在前面是不是已经出现两次了这就不能只看nums[slow]而要看nums[slow - 1]——如果nums[fast]和nums[slow - 1]相同说明 fast 指向的元素已经在数组中出现了至少两次因为 slow - 1 和 slow 是两个相同位置的元素所以这个新元素不能再加入。def removeDuplicates(nums): if not nums: return 0 slow 1 for fast in range(2, len(nums)): if nums[fast] ! nums[slow - 1]: slow 1 nums[slow] nums[fast] return slow 1到这里敏锐的读者可能已经发现规律了如果把“最多保留 k 个”作为一个通用问题那么判断条件就是nums[fast] ! nums[slow - k]。当 k1 时就是 26 题当 k2 时就是 80 题。这个通用模板是我私藏的刷题利器因为它把两道题合并成了一句话def removeDuplicatesK(nums, k): if not nums: return 0 slow 0 for fast in range(len(nums)): if slow k or nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow这个模板的巧妙之处在于slow k保证了数组前 k 个元素不管相不相等都可以直接保留后面再遇到新元素时只要它跟slow - k位置的元素不相等就说明它还没有出现满 k 次可以加入。这个写法我实测过能顺便通过 26、80 两道题面试时如果被问到“扩展到 k 个怎么办”直接甩出这个模板印象分会高很多。2.3 第 217 题“存在重复元素”和 219 题的哈希解法讲完双指针回到基础一点的哈希表。第 217 题是重复元素题的“hello world”——给你一个数组判断是否存在重复元素。最直接的思路当然是哈希集合遍历数组把元素一个一个丢进集合如果发现某个元素已经在集合里就说明有重复。def containsDuplicate(nums): seen set() for num in nums: if num in seen: return True seen.add(num) return False这题的进阶版是 219 题要求不仅存在重复还要求两个重复元素的下标差不超过 k。如果直接套 217 的哈希集合你会发现没法判断下标差。正确做法是哈希表存“元素最后一次出现的下标”遍历时检查当前下标和存储下标的差值是否小于等于 k。def containsNearbyDuplicate(nums, k): pos_map {} for i, num in enumerate(nums): if num in pos_map and i - pos_map[num] k: return True pos_map[num] i return False这里有个细节值得注意哈希表保存的始终是元素最后一次出现的下标。因为最后一次出现一定是最接近当前位置的如果用最早出现的下标判断可能会漏掉中间新出现的重复。我第一次写 219 时用的是if num in pos_map: return True结果发现即使距离超过 k 也会误判后来才意识到要更新下标。这个坑很典型建议你自己跑一遍体会一下。那么问题来了217 能不能不用哈希表当然可以排序后相邻比较就行。排序的时间复杂度是 O(n log n)空间是 O(1)。哈希表是 O(n) 时间、O(n) 空间。在面试中如果追问空间复杂度你就要能从哈希表切换到排序解法并说明两者取舍。3. 链表上的重复元素哑节点和值比较的细节3.1 第 83 题“删除排序链表中的重复元素”保留一个的简单逻辑数组说完来看链表。链表版本的重复元素题和数组版本有个核心差异链表不能按下标随机访问只能从头节点开始一个一个走。但好在题目明确说了是“排序链表”——这意味着相同的节点也是连续排列的所以解法比无序链表简单得多。第 83 题要求删除排序链表中重复的元素每个值保留一个。思路就是用一个指针从头遍历只要当前节点的值和下一个节点的值相同就把下一个节点跳过让当前节点的 next 指向下下个节点否则指针前移继续判断。这个操作不需要哑节点因为头节点本身一定被保留。def deleteDuplicates(head): cur head while cur and cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head注意这里有一个非常容易写错的点当发生删除时cur 不能前移。因为删除后新的cur.next可能还是和当前节点相同的重复节点需要再比较一轮只有当cur.val ! cur.next.val时cur 才移动到下一个节点。我第一次写的时候在 else 分支里忘了这个逻辑把 cur 无条件后移结果遇到连续三个相同节点时就漏删了一个。这个细节在面试时是很容易被面试官抓住的。3.2 第 82 题“删除排序链表中的重复元素 II”重复元素一个不留82 题是 83 题的变体要求把所有重复出现过的元素全部删掉一个都不保留。比如1 - 2 - 2 - 3最后要变成1 - 3。这道题的难度明显上升核心原因在于头节点可能是重复元素如果头节点也被删了你没法直接返回原来的 head。解决思路是引入哑节点dummy node。哑节点的 next 指向头节点这样即使头节点被删我们也能通过 dummy.next 找到新的头节点。然后维护一个 prev 指针它指向“已处理区域的最后一个不重复节点”。遍历时如果当前节点和它的下一个节点值相同就继续往后走把所有相同值的节点全部跳过最后让 prev.next 指向第一个不重复的节点如果当前节点不重复prev 直接前移。def deleteDuplicates(head): dummy ListNode(0, head) prev dummy while head: if head.next and head.val head.next.val: while head.next and head.val head.next.val: head head.next prev.next head.next else: prev prev.next head head.next return dummy.next这段代码里最容易踩的坑是head head.next这行。在“跳过重复段”之后head 已经指向了重复段最后一个节点此时再执行head head.next就正好指向了第一个“不重复的新节点”这个设计是连贯的。但如果你在跳过重复段之后忘了 head 已经指向最后一个重复节点直接写prev.next head.next又写head head.next逻辑就会错乱。建议你把这段代码手动模拟一遍画出每个指针的移动轨迹比任何口头解释都直观。3.3 链表题三连坑空链表、单节点、头节点重复链表相关的题目坑往往不在算法本身而在边界。我总结了自己反复踩的三个坑第一空链表和单节点链表。85% 的链表题都能用while head and head.next这种条件天然规避空指针但如果你提前访问了head.next.val就会直接抛异常。写之前先问自己链表为空时我的代码会不会访问空指针链表只有一个节点时循环会不会进入第二头节点重复无法直接返回。83 题不需要担心这个但 82 题必须用哑节点。这是两道题解法分叉的关键——面试时如果从 83 追问到 82面试官想考察的就是你能不能意识到头节点可能被删除。第三值比较和引用比较混为一谈。链表节点比较的是val还是节点本身在去重场景下当然是 val但如果你写了if head head.next这在某些语言里比较的是引用结果永远为 false程序就会陷入死循环或漏删。我见过不少人在面试现场被这个低级错误卡住非常尴尬。4. 位运算和正负号标记两种“不开额外空间”的巧解4.1 异或运算解决“只出现一次的数字”聊完了通用的哈希表和双指针来说两个“秀操作”性质的解法。第一个是第 136 题“只出现一次的数字”给定一个数组除了某个元素只出现一次其他元素都出现两次找出那个只出现一次的元素。要求线性时间、常数空间。如果不限制空间哈希表就能做。但限制常数空间后很多人的第一反应是“排序再扫描”——排序 O(n log n) 虽然空间 O(1)但时间不满足。这时候位运算登场异或运算有一个神奇的性质相同数字异或为 00 和任何数异或等于那个数本身而且异或满足交换律和结合律。这意味着把数组里所有元素全部异或一遍成对出现的元素会两两抵消变成 0最后剩下的就是那个只出现一次的元素def singleNumber(nums): res 0 for num in nums: res ^ num return res这个解法太优雅了以至于我第一次看到时愣了半天。但我要提醒你这个技巧的适用范围极其有限它只适合“恰好一个元素出现奇数次其他元素出现偶数次”的场景。如果把题目改成“有两个只出现一次的元素”代码就要复杂得多如果改成“有三个重复的”异或就完全失效。所以位运算可以作为加分项展示但不能作为求重复元素的通用武器。4.2 正负号标记法442 和 448 的套路第二个巧解是正负号标记法它专门解决一类特殊条件的题目数组长度为 n元素值在 1 到 n 的范围内。条件这么苛刻是因为它允许我们把数组本身当作哈希表来用——用数值对应下标用正负号作为“是否出现过”的标记。第 442 题“数组中重复的数据”是这类题的代表。遍历数组对于每个数 x abs(nums[i])我们把nums[x - 1]取负。如果某个数已经是负数说明这个下标对应的数字之前出现过也就是重复了。为什么要用 abs因为数组元素在遍历过程中可能已经被改成了负数直接用原始值访问下标会出错。def findDuplicates(nums): res [] for num in nums: idx abs(num) - 1 if nums[idx] 0: res.append(abs(num)) nums[idx] -nums[idx] return res第 448 题“找到所有数组中消失的数字”是同一套路的反向操作先同样做正负号标记然后再次遍历数组找到哪些位置的值仍然为正那些位置的下标加一就是没出现过的数字。这种解法的精妙之处在于把空间复杂度压到了 O(1)但也带来了两个硬前提数组元素必须都在 1 到 n 之间且允许修改原数组。面试时如果你用了这个方法面试官大概率会追问“如果元素范围是 0 到 n-1 呢”——这时候你需要意识到0 作为哨兵值会导致正负号标记失效解法要重新设计。我建议你记住这个方法的适用边界不要机械套用。4.3 正负号标记法在面试中的展示技巧如果你在面试中用到正负号标记法建议你主动说清楚它的前提条件这比默默写出代码效果好得多。我当时面一家公司时面试官出了 442 的变体我写出正负号标记后主动说“这个解法适用于元素范围 1 到 n并且会修改原数组如果题目要求不能修改数组需要改用其他方法。”面试官明显态度不一样还追问了我二分计数的解法。在面试中展示边界意识和方案权衡比单纯写出正确答案更重要。这也侧面说明刷题不只是为了 AC更是为了理解每个解法在什么条件下成立、什么条件下失效。5. 龟兔赛跑和二分计数寻找重复数的进阶玩法5.1 第 287 题如何把数组抽象成链表找环第 287 题“寻找重复数”是重复元素题里的天花板之一也是面试题中的常客。题目描述给定一个包含 n1 个整数的数组整数范围是 1 到 n假设只有一个重复的数字可能重复多次在不修改数组且只用 O(1) 额外空间的条件下找出它。一个很长面熟的解法是排序后找相邻相同但题目不允许修改数组哈希表空间是 O(n)也不行。这个时候把数组看成链表是关键一跳。怎么做呢把数组的每个下标 i 当成链表的节点nums[i]当成从节点 i 出发的 next 指针。因为数组长度为 n1值范围 1 到 n所以从任意位置出发沿着i - nums[i]走一定能走进一个环——环的入口恰好就是重复的那个数。这一步抽象很多人第一次想不到但只要见过一次后面再遇到类似题就容易触类旁通。def findDuplicate(nums): slow nums[0] fast nums[nums[0]] while slow ! fast: slow nums[slow] fast nums[nums[fast]] slow 0 while slow ! fast: slow nums[slow] fast nums[fast] return slow这段代码其实是链表中“寻找环入口”的经典写法只不过把链表访问换成了数组访问。如果你对链表找环不熟悉建议先去做一下 142 题“环形链表 II”把这个解法吃透再来写 287 就顺理成章了。这个解法最难理解的地方是“为什么环的入口就是重复数字”。我尝试用一句话解释因为存在重复数字 x所以至少有两个不同的下标 i 和 j 都满足nums[i] nums[j] x这意味着从这两个下标出发能到达同一个位置形成了一个环在“把数组当下标链表”的模型里所有指向 x 的位置会把快慢指针引向同一点而这个点的数值就是 x。5.2 二分计数另一个不修改数组的解法287 题还有一条完全不依赖链表抽象的路线二分计数。思路是在 [1, n] 范围内二分猜测重复数字每次都统计数组中“小于等于 mid”的数字个数。如果没有重复小于等于 mid 的数字个数应该恰好等于 mid如果实际个数大于 mid说明重复数字在 [1, mid] 区间内否则在 (mid, n] 区间内。def findDuplicate(nums): left, right 1, len(nums) - 1 while left right: mid (left right) // 2 count sum(1 for num in nums if num mid) if count mid: right mid else: left mid 1 return left这个解法的时间复杂度是 O(n log n)空间 O(1)虽然时间上不如龟兔赛跑但胜在思路直观面试时可以作为保底方案。而且它加深了对“重复数字在值域上分布”的理解——重复数字的出现会破坏“小于等于 mid 的数量恰好为 mid”这个规律这是个很重要的观察。5.3 面试官考察 287 题的真正意图287 题在面试中往往不是孤立出现的而是作为“考察你能不能把一个陌生模型映射到已学过的算法”的测试题。数组和链表是两种看似完全不同的数据结构但通过i - nums[i]的映射它们被连通了。能想到这一层的人说明解题时具备抽象建模能力而不仅仅是在套模板。我个人的建议是刷 287 题之前先把 142 题做熟理解快慢指针为什么能找环入口再把 26 题的双指针搞透理解指针移动的本质。287 题是把这些看似不相关的知识点串联起来的一个节点值得花时间去抠细节而不是背代码。6. 实战踩坑记录边界条件、溢出问题和调试习惯6.1 边界条件系统整理一张表避免 80% 的报错刷重复元素题目真正拉开差距的不是算法思路而是边界条件的处理。我把这些题目里最常出现的边界问题整理成一张表面试前扫一眼能省很多时间边界场景涉及题目易犯错误正确做法数组为空26、217、442nums[0]直接越界先判空返回 0 或空列表数组长度为 126、80、136循环条件设置错误直接返回 1 或对应值链表为空 / 单节点83、82访问head.next.val空指针用while head and head.next兜底头节点就是重复元素82return head把头节点也删了用哑节点 dummy最后返回 dummy.next连续重复超过 2 次83删除后 cur 不判断新 next发生删除时 cur 不要前移元素可能为负数220、442取负号时漏加 abs判断和修改时都用 abs值域上界接近 int 上限220t1 溢出 int用 long 类型这张表是从我自己的提交记录里翻出来的每一条都是真实踩过的坑。我最惨的一次是在 220 题上因为t 1溢出导致桶 id 计算错误提交了四次才反应过来。这类问题往往在本地小用例上测不出来因为小数据的 t 很小但 LeetCode 的隐藏用例会把边界值拉满。6.2 第 220 题桶排序的溢出和负数处理220 题“存在重复元素 III”是前文提到的三步曲里难度最高的要求找出是否满足abs(nums[i] - nums[j]) t且abs(i - j) k。哈希表无法处理值差约束有序集合TreeSet时间复杂度 O(n log k)但桶排序可以做到平均 O(n)。桶排序的核心思路是把数值按照“每 t1 一个桶”来分组同桶内的元素差值一定不超过 t。遍历数组时维护一个大小为 k 的滑动窗口窗口内元素按照桶 id 存储。如果当前元素进入的桶已经存在元素直接返回 true否则检查相邻两个桶中是否存在差值不超过 t 的元素。def containsNearbyAlmostDuplicate(nums, k, t): bucket_size t 1 buckets {} for i, num in enumerate(nums): bucket_id num // bucket_size if bucket_id in buckets: return True if bucket_id - 1 in buckets and abs(num - buckets[bucket_id - 1]) t: return True if bucket_id 1 in buckets and abs(num - buckets[bucket_id 1]) t: return True buckets[bucket_id] num if i k: old_id nums[i - k] // bucket_size del buckets[old_id] return False这里有两个必须处理的细节。第一桶大小t 1要用长整型否则当 t 接近 int 上限时会溢出变成负数桶 id 计算全乱套。第二负数在整除时向下取整的问题Python 的//是向下取整所以负数也能得到正确的桶 id但在 Java、C 里整数除法是向零取整负数会分错桶需要用Math.floorDiv或调整(num - min_val) // bucket_size。这个语言差异我在跨语言刷题时踩过一次写完 Python 再写 Java 时差点翻车。6.3 刷重复元素题的调试习惯先暴力再优化最后分享一个比较实用的刷题习惯。遇到重复元素题目我一般不直接上最优解而是先在本地写一个暴力的双层循环版本跑完样例确认自己理解了题意再考虑怎么优化。这个习惯陪我过了很多中等题原因很朴素最优解往往是对暴力解缺陷的修补理解缺陷才能理解优化方向。比如 26 题暴力解法是“从后往前删除重复元素”虽然复杂度高但至少能帮你确认升序、原地、返回长度这三个约束分别意味着什么。确认之后再看快慢指针怎么解决删除导致的 O(n²) 问题就会有“原来如此”的顿悟。反过来如果你一上来就背双指针代码遇到变体题比如“最多保留 k 个”很容易卡住。另外链表题强烈建议你在白纸上画图。画四个节点、标上指针手动模拟 82 题的删除过程比盯着代码空想高效得多。我身边几乎所有算法强的同事面试手撕链表题时都会先画图再写码这个习惯值得你刻意练习。最后分享一点个人体会。重复元素题看起来多而杂但本质上就是“唯一性问题”的不同考法。把哈希表作为第一直觉把双指针、位运算、正负号标记、龟兔赛跑作为特殊条件下的优化手段整个题型的脉络就清晰了。我刷完这一轮的最大收获不是记住了每道题的代码而是养成了一个习惯拿到题目先问自己三个问题——数据是否有序空间是否受限能否修改原数组这三个问题的答案基本就决定了该用哪种解法。你之后做这类题也可以试试这个思路应该能少走不少弯路。
LeetCode重复元素题型全总结：五大解法模型助你秒杀面试
刷 LeetCode 刷到一定量之后你会慢慢发现一个很有意思的现象凡是跟“重复元素”沾边的题不管它挂在哪个标签下面底层解法就那么几板斧——哈希表、排序、双指针、位运算、龟兔赛跑。这周我集中过了一遍 LeetCode 100 Hot 里的相关题目从“存在重复元素”到“寻找重复数”难度从简单一路到偏难但解法模型高度统一。这篇文章就把这些题串起来讲重点不是我贴几份能提交的代码而是帮你建立一个“看到重复元素就知道往哪个方向想”的解题框架。适合谁看一是刚开始刷题、被 217、26、83 这种简单题搞蒙的新手二是刷到中等题想总结套路、准备面试手撕代码的人。文里会涉及数组、链表、哈希表、位运算这些基础数据结构但不会讲太高深的理论所有内容都可以直接在你的编辑器里跑起来验证。1. 重复元素题型的核心脉络一个主题五种解法模型1.1 为什么“重复元素”值得专门写一篇总结你仔细观察 LeetCode 的题单会发现“重复元素”不是某个特定标签下的题目而是横跨数组、链表、哈希表、排序、位运算、二分查找多个分类的题型。这种分散性恰恰是它值得系统总结的原因面试官想考察的往往不是某一个孤立知识点而是你能不能把一个数据结构问题抽象成若干种通用解法。从题目本身看重复元素问题有一个非常明显的特征——几乎所有题目都围绕着“唯一性”做文章。有的题只问“是否存在重复”有的题要求“把重复的删掉”有的题要求“找出那个重复的”还有的题更进一步限定“最多保留 k 个”。这些问题从表面看差异巨大但底层考察的都是同一个能力你能不能高效判断和处理集合中元素的唯一性。我刷完这一批题后最大的感受是重复元素题真正想训练的是两件事第一理解哈希表是解决唯一性问题的第一直觉第二在空间受限或数据有序的特殊条件下怎么用更巧的解法替代哈希表。这两点贯穿了所有重复元素题目也是面试官层层加码考察的核心。1.2 五种解法模型和它们的分工我把重复元素相关题目归纳为六种解法它们在时间复杂度和空间复杂度上有明显差异适用场景也不同。先给你一张速览表后面逐一展开解法模型典型题目时间复杂度空间复杂度核心适用条件哈希表/哈希集合217、219O(n)O(n)最通用最简单的保底方案排序后扫描217 的解法二O(n log n)O(1)可以修改原数组不要求保序双指针26、80O(n)O(1)数组已有序需要原地修改链表哑节点 值比较83、82O(n)O(1)排序链表场景位运算异或136O(n)O(1)恰好存在一个出现奇数次的元素正负号标记442、448O(n)O(1)数组元素范围是 1 到 n龟兔赛跑 / 二分计数287O(n) / O(n log n)O(1)不能修改数组且数值范围明确这张表你可以打印出来贴在显示器边上。实际刷题时看到题目先往表里套大概率能快速锁定方向。接下来我会按常见程度逐个讲清楚其中双指针和链表是面试手撕代码的高频考法篇幅会多一些。2. 数组去重双指针是面试官真正想看的答案2.1 第 26 题“删除有序数组中的重复项”快慢指针的完整拆解这道题是 LeetCode 的简单题也是面试中出现频率极高的一道。题目描述很直接给你一个升序排列的数组要求原地删除重复元素让每个元素只出现一次返回删除后数组的新长度。注意两个约束原地和升序——这基本就是在提示你双指针解法。先想一个问题为什么不能用简单的“遍历 删除”来做因为数组的删除操作是 O(n) 的你每删一个元素后面的所有元素都要往前挪最坏情况下整体复杂度会退化到 O(n²)。而且题目要求“原地”意味着你不能新建一个数组再拷贝回去。双指针的思路其实很生活化想象你手里有两个人一个慢指针 slow 负责在数组前面“圈地”一个快指针 fast 负责在前面探路。slow 记录的是“下一个不重复元素应该放到的位置”fast 则从头到尾扫描整个数组。因为数组有序相同的元素一定连续排列所以只要发现 fast 指向的元素和 slow 位置的元素不同就说明遇到了一个新的不重复元素把它挪到 slow 位置然后 slow 前进一位。def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1注意几个容易出错的地方。第一slow 从 0 开始因为第一个元素无论如何都会保留第二比较的是nums[fast]和nums[slow]而不是nums[fast]和nums[fast - 1]——虽然这两种写法在有序数组上结果一样但前者更好推广到“最多保留 k 个重复项”的通用场景第三返回值是slow 1因为 slow 是最后一个不重复元素的下标长度是下标加一。我第一次写这道题的时候在返回长度上栽过跟头——如果 slow 初始化为 1返回的就是 slow如果初始化为 0返回的就是 slow 1。这个细节看起来不起眼但在面试手撕代码时很容易因为紧张在边界上翻车。建议你固定一种写法比如都从 0 开始最后返回 slow 1这样就只需要记一种模式。2.2 第 80 题“删除有序数组中的重复项 II”从“留一个”到“留 K 个”的通用模板第 80 题是 26 题的升级版这次要求每个元素最多出现两次而不是一次。如果你已经理解 26 题的快慢指针这题其实只改一个条件但很多人就是卡在这个“差一点”上。26 题比较的是nums[fast]和nums[slow]因为 slow 指向的是最后一个保留元素新元素和它不同就说明是最多出现一次。到了 80 题我们需要知道当前元素在前面是不是已经出现两次了这就不能只看nums[slow]而要看nums[slow - 1]——如果nums[fast]和nums[slow - 1]相同说明 fast 指向的元素已经在数组中出现了至少两次因为 slow - 1 和 slow 是两个相同位置的元素所以这个新元素不能再加入。def removeDuplicates(nums): if not nums: return 0 slow 1 for fast in range(2, len(nums)): if nums[fast] ! nums[slow - 1]: slow 1 nums[slow] nums[fast] return slow 1到这里敏锐的读者可能已经发现规律了如果把“最多保留 k 个”作为一个通用问题那么判断条件就是nums[fast] ! nums[slow - k]。当 k1 时就是 26 题当 k2 时就是 80 题。这个通用模板是我私藏的刷题利器因为它把两道题合并成了一句话def removeDuplicatesK(nums, k): if not nums: return 0 slow 0 for fast in range(len(nums)): if slow k or nums[fast] ! nums[slow - k]: nums[slow] nums[fast] slow 1 return slow这个模板的巧妙之处在于slow k保证了数组前 k 个元素不管相不相等都可以直接保留后面再遇到新元素时只要它跟slow - k位置的元素不相等就说明它还没有出现满 k 次可以加入。这个写法我实测过能顺便通过 26、80 两道题面试时如果被问到“扩展到 k 个怎么办”直接甩出这个模板印象分会高很多。2.3 第 217 题“存在重复元素”和 219 题的哈希解法讲完双指针回到基础一点的哈希表。第 217 题是重复元素题的“hello world”——给你一个数组判断是否存在重复元素。最直接的思路当然是哈希集合遍历数组把元素一个一个丢进集合如果发现某个元素已经在集合里就说明有重复。def containsDuplicate(nums): seen set() for num in nums: if num in seen: return True seen.add(num) return False这题的进阶版是 219 题要求不仅存在重复还要求两个重复元素的下标差不超过 k。如果直接套 217 的哈希集合你会发现没法判断下标差。正确做法是哈希表存“元素最后一次出现的下标”遍历时检查当前下标和存储下标的差值是否小于等于 k。def containsNearbyDuplicate(nums, k): pos_map {} for i, num in enumerate(nums): if num in pos_map and i - pos_map[num] k: return True pos_map[num] i return False这里有个细节值得注意哈希表保存的始终是元素最后一次出现的下标。因为最后一次出现一定是最接近当前位置的如果用最早出现的下标判断可能会漏掉中间新出现的重复。我第一次写 219 时用的是if num in pos_map: return True结果发现即使距离超过 k 也会误判后来才意识到要更新下标。这个坑很典型建议你自己跑一遍体会一下。那么问题来了217 能不能不用哈希表当然可以排序后相邻比较就行。排序的时间复杂度是 O(n log n)空间是 O(1)。哈希表是 O(n) 时间、O(n) 空间。在面试中如果追问空间复杂度你就要能从哈希表切换到排序解法并说明两者取舍。3. 链表上的重复元素哑节点和值比较的细节3.1 第 83 题“删除排序链表中的重复元素”保留一个的简单逻辑数组说完来看链表。链表版本的重复元素题和数组版本有个核心差异链表不能按下标随机访问只能从头节点开始一个一个走。但好在题目明确说了是“排序链表”——这意味着相同的节点也是连续排列的所以解法比无序链表简单得多。第 83 题要求删除排序链表中重复的元素每个值保留一个。思路就是用一个指针从头遍历只要当前节点的值和下一个节点的值相同就把下一个节点跳过让当前节点的 next 指向下下个节点否则指针前移继续判断。这个操作不需要哑节点因为头节点本身一定被保留。def deleteDuplicates(head): cur head while cur and cur.next: if cur.val cur.next.val: cur.next cur.next.next else: cur cur.next return head注意这里有一个非常容易写错的点当发生删除时cur 不能前移。因为删除后新的cur.next可能还是和当前节点相同的重复节点需要再比较一轮只有当cur.val ! cur.next.val时cur 才移动到下一个节点。我第一次写的时候在 else 分支里忘了这个逻辑把 cur 无条件后移结果遇到连续三个相同节点时就漏删了一个。这个细节在面试时是很容易被面试官抓住的。3.2 第 82 题“删除排序链表中的重复元素 II”重复元素一个不留82 题是 83 题的变体要求把所有重复出现过的元素全部删掉一个都不保留。比如1 - 2 - 2 - 3最后要变成1 - 3。这道题的难度明显上升核心原因在于头节点可能是重复元素如果头节点也被删了你没法直接返回原来的 head。解决思路是引入哑节点dummy node。哑节点的 next 指向头节点这样即使头节点被删我们也能通过 dummy.next 找到新的头节点。然后维护一个 prev 指针它指向“已处理区域的最后一个不重复节点”。遍历时如果当前节点和它的下一个节点值相同就继续往后走把所有相同值的节点全部跳过最后让 prev.next 指向第一个不重复的节点如果当前节点不重复prev 直接前移。def deleteDuplicates(head): dummy ListNode(0, head) prev dummy while head: if head.next and head.val head.next.val: while head.next and head.val head.next.val: head head.next prev.next head.next else: prev prev.next head head.next return dummy.next这段代码里最容易踩的坑是head head.next这行。在“跳过重复段”之后head 已经指向了重复段最后一个节点此时再执行head head.next就正好指向了第一个“不重复的新节点”这个设计是连贯的。但如果你在跳过重复段之后忘了 head 已经指向最后一个重复节点直接写prev.next head.next又写head head.next逻辑就会错乱。建议你把这段代码手动模拟一遍画出每个指针的移动轨迹比任何口头解释都直观。3.3 链表题三连坑空链表、单节点、头节点重复链表相关的题目坑往往不在算法本身而在边界。我总结了自己反复踩的三个坑第一空链表和单节点链表。85% 的链表题都能用while head and head.next这种条件天然规避空指针但如果你提前访问了head.next.val就会直接抛异常。写之前先问自己链表为空时我的代码会不会访问空指针链表只有一个节点时循环会不会进入第二头节点重复无法直接返回。83 题不需要担心这个但 82 题必须用哑节点。这是两道题解法分叉的关键——面试时如果从 83 追问到 82面试官想考察的就是你能不能意识到头节点可能被删除。第三值比较和引用比较混为一谈。链表节点比较的是val还是节点本身在去重场景下当然是 val但如果你写了if head head.next这在某些语言里比较的是引用结果永远为 false程序就会陷入死循环或漏删。我见过不少人在面试现场被这个低级错误卡住非常尴尬。4. 位运算和正负号标记两种“不开额外空间”的巧解4.1 异或运算解决“只出现一次的数字”聊完了通用的哈希表和双指针来说两个“秀操作”性质的解法。第一个是第 136 题“只出现一次的数字”给定一个数组除了某个元素只出现一次其他元素都出现两次找出那个只出现一次的元素。要求线性时间、常数空间。如果不限制空间哈希表就能做。但限制常数空间后很多人的第一反应是“排序再扫描”——排序 O(n log n) 虽然空间 O(1)但时间不满足。这时候位运算登场异或运算有一个神奇的性质相同数字异或为 00 和任何数异或等于那个数本身而且异或满足交换律和结合律。这意味着把数组里所有元素全部异或一遍成对出现的元素会两两抵消变成 0最后剩下的就是那个只出现一次的元素def singleNumber(nums): res 0 for num in nums: res ^ num return res这个解法太优雅了以至于我第一次看到时愣了半天。但我要提醒你这个技巧的适用范围极其有限它只适合“恰好一个元素出现奇数次其他元素出现偶数次”的场景。如果把题目改成“有两个只出现一次的元素”代码就要复杂得多如果改成“有三个重复的”异或就完全失效。所以位运算可以作为加分项展示但不能作为求重复元素的通用武器。4.2 正负号标记法442 和 448 的套路第二个巧解是正负号标记法它专门解决一类特殊条件的题目数组长度为 n元素值在 1 到 n 的范围内。条件这么苛刻是因为它允许我们把数组本身当作哈希表来用——用数值对应下标用正负号作为“是否出现过”的标记。第 442 题“数组中重复的数据”是这类题的代表。遍历数组对于每个数 x abs(nums[i])我们把nums[x - 1]取负。如果某个数已经是负数说明这个下标对应的数字之前出现过也就是重复了。为什么要用 abs因为数组元素在遍历过程中可能已经被改成了负数直接用原始值访问下标会出错。def findDuplicates(nums): res [] for num in nums: idx abs(num) - 1 if nums[idx] 0: res.append(abs(num)) nums[idx] -nums[idx] return res第 448 题“找到所有数组中消失的数字”是同一套路的反向操作先同样做正负号标记然后再次遍历数组找到哪些位置的值仍然为正那些位置的下标加一就是没出现过的数字。这种解法的精妙之处在于把空间复杂度压到了 O(1)但也带来了两个硬前提数组元素必须都在 1 到 n 之间且允许修改原数组。面试时如果你用了这个方法面试官大概率会追问“如果元素范围是 0 到 n-1 呢”——这时候你需要意识到0 作为哨兵值会导致正负号标记失效解法要重新设计。我建议你记住这个方法的适用边界不要机械套用。4.3 正负号标记法在面试中的展示技巧如果你在面试中用到正负号标记法建议你主动说清楚它的前提条件这比默默写出代码效果好得多。我当时面一家公司时面试官出了 442 的变体我写出正负号标记后主动说“这个解法适用于元素范围 1 到 n并且会修改原数组如果题目要求不能修改数组需要改用其他方法。”面试官明显态度不一样还追问了我二分计数的解法。在面试中展示边界意识和方案权衡比单纯写出正确答案更重要。这也侧面说明刷题不只是为了 AC更是为了理解每个解法在什么条件下成立、什么条件下失效。5. 龟兔赛跑和二分计数寻找重复数的进阶玩法5.1 第 287 题如何把数组抽象成链表找环第 287 题“寻找重复数”是重复元素题里的天花板之一也是面试题中的常客。题目描述给定一个包含 n1 个整数的数组整数范围是 1 到 n假设只有一个重复的数字可能重复多次在不修改数组且只用 O(1) 额外空间的条件下找出它。一个很长面熟的解法是排序后找相邻相同但题目不允许修改数组哈希表空间是 O(n)也不行。这个时候把数组看成链表是关键一跳。怎么做呢把数组的每个下标 i 当成链表的节点nums[i]当成从节点 i 出发的 next 指针。因为数组长度为 n1值范围 1 到 n所以从任意位置出发沿着i - nums[i]走一定能走进一个环——环的入口恰好就是重复的那个数。这一步抽象很多人第一次想不到但只要见过一次后面再遇到类似题就容易触类旁通。def findDuplicate(nums): slow nums[0] fast nums[nums[0]] while slow ! fast: slow nums[slow] fast nums[nums[fast]] slow 0 while slow ! fast: slow nums[slow] fast nums[fast] return slow这段代码其实是链表中“寻找环入口”的经典写法只不过把链表访问换成了数组访问。如果你对链表找环不熟悉建议先去做一下 142 题“环形链表 II”把这个解法吃透再来写 287 就顺理成章了。这个解法最难理解的地方是“为什么环的入口就是重复数字”。我尝试用一句话解释因为存在重复数字 x所以至少有两个不同的下标 i 和 j 都满足nums[i] nums[j] x这意味着从这两个下标出发能到达同一个位置形成了一个环在“把数组当下标链表”的模型里所有指向 x 的位置会把快慢指针引向同一点而这个点的数值就是 x。5.2 二分计数另一个不修改数组的解法287 题还有一条完全不依赖链表抽象的路线二分计数。思路是在 [1, n] 范围内二分猜测重复数字每次都统计数组中“小于等于 mid”的数字个数。如果没有重复小于等于 mid 的数字个数应该恰好等于 mid如果实际个数大于 mid说明重复数字在 [1, mid] 区间内否则在 (mid, n] 区间内。def findDuplicate(nums): left, right 1, len(nums) - 1 while left right: mid (left right) // 2 count sum(1 for num in nums if num mid) if count mid: right mid else: left mid 1 return left这个解法的时间复杂度是 O(n log n)空间 O(1)虽然时间上不如龟兔赛跑但胜在思路直观面试时可以作为保底方案。而且它加深了对“重复数字在值域上分布”的理解——重复数字的出现会破坏“小于等于 mid 的数量恰好为 mid”这个规律这是个很重要的观察。5.3 面试官考察 287 题的真正意图287 题在面试中往往不是孤立出现的而是作为“考察你能不能把一个陌生模型映射到已学过的算法”的测试题。数组和链表是两种看似完全不同的数据结构但通过i - nums[i]的映射它们被连通了。能想到这一层的人说明解题时具备抽象建模能力而不仅仅是在套模板。我个人的建议是刷 287 题之前先把 142 题做熟理解快慢指针为什么能找环入口再把 26 题的双指针搞透理解指针移动的本质。287 题是把这些看似不相关的知识点串联起来的一个节点值得花时间去抠细节而不是背代码。6. 实战踩坑记录边界条件、溢出问题和调试习惯6.1 边界条件系统整理一张表避免 80% 的报错刷重复元素题目真正拉开差距的不是算法思路而是边界条件的处理。我把这些题目里最常出现的边界问题整理成一张表面试前扫一眼能省很多时间边界场景涉及题目易犯错误正确做法数组为空26、217、442nums[0]直接越界先判空返回 0 或空列表数组长度为 126、80、136循环条件设置错误直接返回 1 或对应值链表为空 / 单节点83、82访问head.next.val空指针用while head and head.next兜底头节点就是重复元素82return head把头节点也删了用哑节点 dummy最后返回 dummy.next连续重复超过 2 次83删除后 cur 不判断新 next发生删除时 cur 不要前移元素可能为负数220、442取负号时漏加 abs判断和修改时都用 abs值域上界接近 int 上限220t1 溢出 int用 long 类型这张表是从我自己的提交记录里翻出来的每一条都是真实踩过的坑。我最惨的一次是在 220 题上因为t 1溢出导致桶 id 计算错误提交了四次才反应过来。这类问题往往在本地小用例上测不出来因为小数据的 t 很小但 LeetCode 的隐藏用例会把边界值拉满。6.2 第 220 题桶排序的溢出和负数处理220 题“存在重复元素 III”是前文提到的三步曲里难度最高的要求找出是否满足abs(nums[i] - nums[j]) t且abs(i - j) k。哈希表无法处理值差约束有序集合TreeSet时间复杂度 O(n log k)但桶排序可以做到平均 O(n)。桶排序的核心思路是把数值按照“每 t1 一个桶”来分组同桶内的元素差值一定不超过 t。遍历数组时维护一个大小为 k 的滑动窗口窗口内元素按照桶 id 存储。如果当前元素进入的桶已经存在元素直接返回 true否则检查相邻两个桶中是否存在差值不超过 t 的元素。def containsNearbyAlmostDuplicate(nums, k, t): bucket_size t 1 buckets {} for i, num in enumerate(nums): bucket_id num // bucket_size if bucket_id in buckets: return True if bucket_id - 1 in buckets and abs(num - buckets[bucket_id - 1]) t: return True if bucket_id 1 in buckets and abs(num - buckets[bucket_id 1]) t: return True buckets[bucket_id] num if i k: old_id nums[i - k] // bucket_size del buckets[old_id] return False这里有两个必须处理的细节。第一桶大小t 1要用长整型否则当 t 接近 int 上限时会溢出变成负数桶 id 计算全乱套。第二负数在整除时向下取整的问题Python 的//是向下取整所以负数也能得到正确的桶 id但在 Java、C 里整数除法是向零取整负数会分错桶需要用Math.floorDiv或调整(num - min_val) // bucket_size。这个语言差异我在跨语言刷题时踩过一次写完 Python 再写 Java 时差点翻车。6.3 刷重复元素题的调试习惯先暴力再优化最后分享一个比较实用的刷题习惯。遇到重复元素题目我一般不直接上最优解而是先在本地写一个暴力的双层循环版本跑完样例确认自己理解了题意再考虑怎么优化。这个习惯陪我过了很多中等题原因很朴素最优解往往是对暴力解缺陷的修补理解缺陷才能理解优化方向。比如 26 题暴力解法是“从后往前删除重复元素”虽然复杂度高但至少能帮你确认升序、原地、返回长度这三个约束分别意味着什么。确认之后再看快慢指针怎么解决删除导致的 O(n²) 问题就会有“原来如此”的顿悟。反过来如果你一上来就背双指针代码遇到变体题比如“最多保留 k 个”很容易卡住。另外链表题强烈建议你在白纸上画图。画四个节点、标上指针手动模拟 82 题的删除过程比盯着代码空想高效得多。我身边几乎所有算法强的同事面试手撕链表题时都会先画图再写码这个习惯值得你刻意练习。最后分享一点个人体会。重复元素题看起来多而杂但本质上就是“唯一性问题”的不同考法。把哈希表作为第一直觉把双指针、位运算、正负号标记、龟兔赛跑作为特殊条件下的优化手段整个题型的脉络就清晰了。我刷完这一轮的最大收获不是记住了每道题的代码而是养成了一个习惯拿到题目先问自己三个问题——数据是否有序空间是否受限能否修改原数组这三个问题的答案基本就决定了该用哪种解法。你之后做这类题也可以试试这个思路应该能少走不少弯路。