1. 重复元素题目到底在考什么1.1 一个高频考点的四种面孔LeetCode热题100里重复元素相关的题几乎可以说是“入门第一关”。不少刚开始刷题的人第一天就会撞上26题、217题、136题这些名字然后发现题目描述看似相似解法却天差地别有的用双指针有的用哈希表有的用位运算还有的要用快慢指针。我当时刷到这些题的时候也困惑过它们到底是一类题还是纯粹的撞名被面试官问多了之后、把整个系列刷完一遍回头看我才逐渐摸清楚所谓“重复元素”在LeetCode里其实能分成四条截然不同的线路第一类有序结构原地去重代表题是26题“删除有序数组中的重复项”、80题“删除有序数组中的重复项 II”以及83、82题“删除排序链表中的重复元素”。这类题的关键词是“原地”、“相对顺序”本质上考的是双指针和链表指针操作。第二类判断是否存在重复代表题是217题“存在重复元素”和219题“存在重复元素 II”核心考点是哈希表与滑动窗口。第三类在“只有一个/两个数字是不重复/重复”的约束下找目标代表题是136题“只出现一次的数字”和287题“寻找重复数”核心考点是位运算和快慢指针。第四类和“重复元素”相关但站在不同角度比如442题“数组中重复的数据”、645题“错误的集合”等等。把这些题放在一起看会发现它们的高频出现并不是偶然。“重复元素”本质上是哈希表、双指针、位运算、链表操作四大基础技能的交叉题目面试官只需要换一个外壳就能在同一套知识点上反复考察候选人。所以把这一个系列吃透比零散刷几十道题性价比高得多。这篇文章适合正在刷LeetCode但还没形成体系的新手也适合准备面试想快速过一遍高频题的小伙伴。我会按题型逐类拆解把每道题的解题思路、代码实现、边界条件和踩坑点都过一遍。1.2 这类题的通用思考框架刷多了以后我觉得“重复元素”这四个字的最佳破题方式是先问自己三个问题而不是上来就想解法。第一个问题数据本身有序吗有序就意味着“相同元素必然相邻”可以尝试双指针、扫描一次解决。无序则大概率要走哈希表或者先排序再处理。这个判断直接决定了算法复杂度的下限。第二个问题空间复杂度有没有限制题目里一旦出现“原地”“常数空间”这类词基本就说明面试官希望你不用额外哈希表要么用指针挪动要么用位运算要么用原地标记。第三个问题有没有数字范围的额外条件比如287题里“n1个数字都在1到n之间”这个条件看着不起眼实际上直接指向了“把数组看成链表、用快慢指针找环入口”这种神奇解法。442题的“1 ≤ a[i] ≤ n”同样暗示可以用下标取负做原地标记。顺着这三个问题去套大多数重复元素的题目都能在三分钟内定位到正确的核心思路。我把这个框架叫“三问破题法”后面讲每道题的时候都会反复用到它。2. 有序数组去重双指针的精髓2.1 26题删除有序数组中的重复项快指针探路、慢指针写位26题是LeetCode的原题也是“重复元素”系列的敲门砖。题目要求给定一个升序排列的数组原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。关键限制是不能额外开辟数组空间只能修改原数组。我第一次写这题的时候第一反应是“把重复的标记出来再一次性挪动”结果写了一堆循环不是下标越界就是顺序乱了。后来看优秀题解才明白这题的正确姿势是快慢双指针。快指针的作用相当于一个侦察兵从头到尾扫描每个元素慢指针则像一个后勤官只在需要保留元素时才移动。核心逻辑其实一句话就能说清楚快指针遍历整个数组只要发现nums[fast] ! nums[slow]就说明遇到了一个“新元素”于是慢指针先加一再用这个新元素覆盖慢指针指向的位置。最后数组的前slow 1个位置就是去重后的结果返回slow 1就是新长度。class Solution: def removeDuplicates(self, nums: List[int]) - int: 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这段代码有几点值得注意。第一是fast从1开始而不是0因为nums[0]本身就可以直接作为去重后的第一个元素。第二是为什么可以放心覆盖nums[slow 1]因为fast永远跑在slow前面覆盖的位置一定已经被快指针扫描过了不会丢失任何还没处理的元素。生活化的类比是这样的想象一条单行道上排列着相同颜色的车队慢指针坐在指挥车里快指针是前面的侦察车。侦察车每看到一辆“颜色不同”的车指挥车就往前开一格让侦察车把后面那辆新车开到自己旁边。顺序没有被破坏因为指挥车永远不越过侦察车。我在LeetCode上跑这段代码时间复杂度和空间复杂度分别是O(n)和O(1)。这题还有一种变形是“最多保留k个重复元素”模板化的写法我放到下一节讲。2.2 80题每个元素最多保留两次把“去重”扩展成“限频”26题做完之后马上会遇到它的加强版——80题“删除有序数组中的重复项 II”。题目不再要求“每个元素只出现一次”而是允许“每个元素最多出现两次”比如输入[1,1,1,2,2,3]输出应该是[1,1,2,2,3]返回长度5。如果26题的快慢指针你理解了80题其实很容易推广。26题比较的是nums[fast]和nums[slow]因为它们只要不同就保留80题要允许两个相同的元素存在所以判断条件变成了nums[fast] ! nums[slow - 1]。为什么是slow - 1而不是slow - 2因为slow是“下一个待写入的位置”slow - 1是“最后一个已经被保留的元素”slow - 2是“倒数第二个被保留的元素”。我们检查的是“当前快指针元素”是否已经出现够两次了如果nums[fast]和nums[slow - 2]相同说明至少已经有了两个一样的值新元素不能再要了如果不同说明前两个位置里至少有一个不同于当前值可以放心保留。class Solution: def removeDuplicates(self, nums: List[int]) - int: if len(nums) 2: return len(nums) slow 2 for fast in range(2, len(nums)): if nums[fast] ! nums[slow - 2]: nums[slow] nums[fast] slow 1 return slow这个写法比写专项判断要优雅多了而且可以直接推广到“每个元素最多保留k个”的通用场景把slow初始化为k循环从k开始比较nums[fast]和nums[slow - k]。面试的时候如果能写出这个通用版本通常会让面试官眼前一亮。踩坑提醒80题最容易出事的地方是长度判断——当数组长度小于等于2时直接返回原长度即可不然slow - 2会访问越界。我当时就是没加这行交上去错了两次才反应过来。2.3 双指针写法背后的设计原因为什么有序数组去重天然适合双指针这和数组的内存连续性分不开。数组里的元素物理上扎堆存储删除一个元素需要把后面所有元素往前挪动平均时间复杂度是O(n)。双指针之所以高效是因为它把“删除”偷换成了“覆盖”——不需要真正把旧元素清掉只需要把“值得保留的元素”依次写到前面后面的冗余元素自然被忽略。这个思路有个隐含前提题目只要求返回新长度并允许数组尾部残留废弃数据。换句话说双指针是在跟题目规则做交易——我用“尾部脏数据”换“一次遍历完成去重”。LeetCode的判题逻辑也允许这一点因为只有前k个元素会被核对。面试时如果觉得双指针不好理解可以先讲暴力解法每遇到一个重复值就把后面元素整体前移一次。然后分析它为什么慢——每删一个元素都要移动O(n)个元素整体复杂度O(n²)——再自然过渡到双指针优化。这种“先暴力、再优化”的讲述模式本身也是面试官喜欢看到的思考路径。3. 链表重复元素的删除指针操作与前置节点3.1 83题删除排序链表中的重复元素数组去重考的是双指针链表去重考的就是指针操作典型代表是83题“删除排序链表中的重复元素”。题目给的是一个已排序的链表要求删除所有重复元素让每个元素只出现一次。链表题和数组题有一个本质区别链表没有下标不能随机访问只能顺着next指针一个个走。所以能用的“指针”天然就落在链表节点上。这题的解法非常直观用一个cur指针从头遍历只要cur.next存在且cur.val cur.next.val就让cur.next cur.next.next把重复节点直接跳过否则cur cur.next继续往后走。class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: 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跳过重复节点。原因是“可能一连串都是同样的值”比如1 - 1 - 1 - 2如果遇到第一个1和第二个1相同就直接移动cur那第三个1又需要再处理一次代码也能跑对但逻辑上不如“留在原地、继续让下一个节点和当前节点比较”清晰。我见过不少新手把if误写成while其实在这个写法里if就够了因为跳过一个相等节点后新的cur.next还要继续和cur比较天然就是一个循环过程。还有一个易错点处理完链表之后要记得return head而不是return cur。因为cur在循环结束时已经指向了链表尾部的空节点直接返回会丢掉整个链表。这个错误我在初学链表题时犯过不止一次每次都是在测试用例只有一两个节点时才暴露出来特别有迷惑性。3.2 82题一个都不留删除全部重复元素83题是“每个数字留一个”82题则反过来——“只要这个值出现过重复就一个都不留”。输入1 - 2 - 3 - 3 - 4 - 4 - 5输出1 - 2 - 5输入1 - 1 - 1 - 2 - 3输出2 - 3。这一题对指针操作的要求明显上了一个台阶。因为头节点本身也可能被删掉所以不能直接返回传入的head需要引入一个虚拟头节点dummy让dummy.next head。这样即使真正的头节点被删除我们也有一条链子可以从dummy出发找到新的头部。核心写法是用一个cur指针从dummy开始每次判断cur.next和cur.next.next的值是否相等。注意这里比较的不再是“当前节点”和“下一个节点”而是“下一个”和“下下一个”因为cur本身指向的是“上一个已经被确定保留的节点”它的下一个节点是否保留需要看再后面的节点。如果cur.next.val ! cur.next.next.val说明cur.next是唯一的直接cur cur.next如果相等就需要找到这一段重复区域的末尾把这些重复节点全部跳过。class Solution: def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0, head) cur dummy while cur.next and cur.next.next: if cur.next.val cur.next.next.val: val cur.next.val while cur.next and cur.next.val val: cur.next cur.next.next else: cur cur.next return dummy.next这段代码最关键的技巧是一旦发现重复值val就再用一个内层while把所有值等于val的节点全部跳过然后让cur保持在原地不动。为什么要留在原地因为跳完这一整段重复值之后cur.next指向的是一个“可能要继续判断”的新节点它也可能和后面是重复的所以不能急着把cur往后移。我最早写这题的时候把cur.next cur.next.next写成了cur cur.next结果逻辑完全乱了。后来总结经验在链表删除场景里如果前驱节点位置不稳定永远要让“前驱节点”去操作它的next而不是自己乱动。3.3 链表去重为什么需要虚拟头节点字节、微软、美团这类大厂的面试题里82题是非常经典的“链表指针操作”考察题。面试官通常还会追加一个反问为什么这里要引入dummy答案的核心在于“头节点可能会被删除”。在83题里头节点一定不会被删因为它是第一个出现的数字即使后面有相同值保留的也是它。但82题里只要头节点的值和后面重复头节点就得一起删。如果没有dummy我们就要单独处理“删除头节点”的分支逻辑代码会变得非常啰嗦而且容易出错。引入一个永远不被删除、也没有实际含义的虚拟头节点之后所有节点被统一对待逻辑上更干净代码也更短。还有一个细节dummy的val可以随便设置因为永远不会被读取dummy.next要正确指向原链表头部。返回时必须是dummy.next因为原head可能已经不在链表里了。面试时如果这里回答得流利通常会加分。4. 存在重复元素系列哈希法与排序法4.1 217题一次遍历哈希表判重数组去重和链表去重都是“修改结构”而217题“存在重复元素”是纯粹的“判断题”给定一个数组只要任意一个元素出现至少两次就返回true否则返回false。题目没有顺序限制没有空间限制也不需要保留元素所以解法空间非常大。最容易想到的是暴力双重循环每对元素都比较一次复杂度O(n²)太慢了。稍微好一点的是先排序再相邻比较排序复杂度O(n log n)排完序后扫描一遍只要发现相邻元素相等就能返回true。但排序会修改原数组题目虽然没禁止面试时通常不是首选。最常规也最稳定的方案是哈希表遍历数组把每个元素放进一个set放进之前先检查它是否已经存在。如果存在直接返回true否则继续遍历。时间复杂度O(n)空间复杂度O(n)代码短到只有几行class Solution: def containsDuplicate(self, nums: List[int]) - bool: seen set() for num in nums: if num in seen: return True seen.add(num) return FalsePython里set的判断是哈希查找平均时间复杂度O(1)。所以整个算法是线性的。很多人会进一步优化成return len(nums) ! len(set(nums))——一行代码搞定。这个写法在LeetCode上是可以通过的但它有个小问题数组很大的时候把整个数组转成set其实会做一些多余的哈希操作而且等数组已经全部处理完才知道答案不像遍历过程中“提前返回”那样可能提前结束。不过笔试和面试里用法都很多看个人偏好。这题最值得记的是“去重”和“判重”的思路切换数组去重题里我们关心保留哪些元素、顺序怎么保持判重题里我们只关心“有没有重复”不关心具体重复了几次、在哪出现。想清楚这一点代码就不容易写复杂。4.2 219题升级版限制距离的滑动窗口219题“存在重复元素 II”加了一个新的约束不仅要求数组里存在两个相同的元素还要求它们的下标差不超过k。换句话说要在数组里找一对i j满足nums[i] nums[j]且j - i k。如果沿用217题的思路仍然可以用哈希表只不过set要升级成“字典”key存元素值value存最后一次出现的下标。遍历数组时如果发现当前元素已经在字典里就检查当前下标 - 上一次出现下标是否小于等于k如果满足直接返回true。不管满不满足都要把当前下标更新到字典里。class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) - bool: pos {} for i, num in enumerate(nums): if num in pos and i - pos[num] k: return True pos[num] i return False为什么即使距离超过k也要更新下标因为i越来越大旧下标和未来的新下标差距只会更大永远不可能满足约束所以“保旧”没有意义必须往最新的位置看齐。还有一种思路是维护一个大小固定为k 1的滑动窗口窗口内保证只有“可能满足距离约束”的元素。遍历时先检查当前元素是否已经在窗口内然后加入窗口如果窗口大小超过k 1就弹出最老的元素。这种做法只是把哈希表换了一种组织方式本质上和字典解法等价的。我个人觉得字典解法更好写也不容易出边界问题面试时优先推荐。4.3 寻找重复数把数组当成链表来走287题“寻找重复数”是整个系列里比较有深度的一道题。题目给一个包含n 1个整数的数组数字都在1到n之间假设只有一个数字重复要求找出这个重复数字。而且题目通常附带一个硬要求不能修改数组只能使用O(1)额外空间。看到“不能修改数组、O(1)空间”这两个限制哈希表和排序就全被禁了。那怎么找重复很多第一次接触这题的人会懵住我也是看了题解才明白这个约束条件其实是在暗示可以用“快慢指针找环入口”的思路。具体原理是这样的把数组每个位置的下标当成链表节点把nums[i]当成指向下一个节点的指针那么从0号下标开始访问就会形成一个“链表”。由于数组长度为n 1而值域是1到n至少有两个位置指向同一个值也就是说这个“链表”里一定存在环。环的入口节点恰恰就是那个重复出现的数字。既然有环就可以用Floyd判圈算法快指针每次走两步慢指针每次走一步两个指针在环里必定相遇。相遇后再用一个指针从头出发另一个从相遇点出发每次都走一步再次相遇的位置就是环的入口节点。class Solution: def findDuplicate(self, nums: List[int]) - int: 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代码很短但理解它需要一定门槛。我第一次看到这个解法时几乎是硬背下来的后来才慢慢理解背后的数学原理快慢指针首次相遇时相遇点距离环入口的距离等于链表起点到环入口的距离。所以用一个指针从头出发另一个从相遇点出发同步前进就会在环入口相遇。面试时如果时间充裕还可以提一下二分法解法因为值域固定是1到n二分区间的左半部分元素数量如果超过区间长度就说明重复值在左半区否则在右半区。每轮遍历一次数组统计计数器复杂度O(n log n)。这个解法虽然不是最优但体现了不同思路通常能展示思维的广度。4.4 只出现一次的数字位运算去重一个循环搞定136题“只出现一次的数字”同样属于“重复元素”的亲戚。题目说给定一个数组除了某个元素只出现一次外其余每个元素都恰好出现两次找出那个“只出现一次”的元素。这题的经典解法简直帅到没朋友把所有数字异或在一起。因为同一个数字异或两次会相互抵消变成0而任何数异或0还是它本身。所以全部异或的结果就是那个只出现一次的数字。class Solution: def singleNumber(self, nums: List[int]) - int: res 0 for num in nums: res ^ num return res这个解法巧妙的地方在于它完全利用了“成对出现的重复元素”这一特殊约束。如果题目改成“有两个数字只出现一次”这个解法就需要进一步升级成“按位分组异或”的思路。所以面试官特别喜欢顺势抛出一个变种题看看你会不会举一反三。异或运算有三个性质值得记住交换律、结合律以及x ^ x 0、x ^ 0 x。这三条性质组合起来就是位运算去重的全部秘密。生活化的类比是“图书馆的还书系统”一本书被两个人借走每次借出、还回都登记一次最后剩下的那个没登记两次的就是唯一没被借走的书。5. 踩坑总结与面试避坑指南5.1 常见问题速查表刷完这一系列重复元素题目我把容易踩的坑按题型整理了一下题目高频错误正确的解决姿势26题 数组去重忘记判空数组返回slow而不是slow 1先if not nums: return 0新长度是slow 180题 最多保留两个重复数组长度小于2时越界初始比较用slow - 1而不是slow - 2长度小于等于2直接返回要允许出现两次比较窗口得往前多看一个位置83题 链表去重误用while导致跳过多个重复返回cur而不是headif判断即可因为跳完一个还要继续判断始终返回最初保存的头节点82题 链表全部删除忘记dummy节点导致头节点删除逻辑混乱内层循环写错导致跳不干净始终从dummy出发操作前驱用变量val记录当前重复值用一个内层循环把所有相同节点一次性删干净217题 存在重复元素用排序后再判断时修改了原数组用set判重空间换时间219题 存在重复元素 II只记录第一次出现下标导致距离判断错误每次遍历都更新元素的最新下标因为旧下标不可能再满足距离约束287题 寻找重复数试图用排序或哈希表打破空间限制用快慢指针找环入口或二分值域136题 只出现一次的数字用哈希表存储计数忽略了位运算解法全部异或即可需要注意一个数字对应二进制每一位都要异或处理我发现一个挺有意思的规律这几道题的错误模式高度集中在“边界条件”和“返回值”上。说明LeetCode的数组和链表题最喜欢在边界处埋雷——数组的长度为0、1、2链表的空链表、单节点、头节点被删这些情况你只要多测几组正确率能提升一大截。5.2 刷题与面试方案速记如果时间紧、准备面试我建议按这个顺序来刷第一梯队26题 217题 136题。这三题覆盖了双指针、哈希表、位运算三大核心技法每题代码都很短适合作为热身。第二梯队80题 83题 82题。把“重复元素”从数组扩展到链表目的是训练指针操作。第三梯队219题 287题。这两题需要你跳出“常规解法”前者考滑动窗口后者考快慢指针找环。我自己的刷题习惯是每道题至少写两遍第二遍尝试不看题解白板手写。整个过程下来感觉对“重复元素”的理解会从“背题目”升级到“看穿套路”。面试中如果遇到变形题不用慌拿出“三问破题法”有序吗原地/常数空间吗有没有数值范围条件三个问题一问完思路基本就锁定了。5.3 面试时怎么把答案讲得漂亮会做题是一回事能把思路讲清楚是另一回事。我在面试别人时最怕看到候选人突然抛出一段“神仙写法”却说不出为什么。所以这里分享几个表达技巧先讲最笨的解法再讲优化。比如26题先承认“可以新开数组把所有不重复的值copy进去”然后分析“这样空间复杂度O(n)题目要求O(1)不行”再过渡到快慢指针。这个过程会让面试官看到你的分析路径而不是直接背答案。讲双指针时先把快慢指针各自负责什么说清楚。我习惯用“快指针负责发现慢指针负责存放”这句话来概括面试官通常反应不错。讲哈希表时先说清“用空间换时间”的取舍再解释为什么哈希表的查找是O(1)。另外很多候选人会在刷题时忽略一道题可以“一题多解”。比如217题如果你只说哈希表面试官可能马上追问“如果空间复杂度限制为O(1)呢”如果提前准备了排序解法就能从容应对。还有个小技巧面试时写代码前先把边界条件列出来口头说一遍。比如“数组长度为0直接返回0”“链表为空直接返回null”“如果长度小于等于2直接返回原长度”。这会让面试官觉得你思路很严密是一个不容易漏边界的人。哪怕最后代码里忘了加判断面试官至少看到了你的意识通常会给一些提示。遇到短小的“魔法解法”比如136题的异或不要只写代码先问一下“我可不可以先用暴力解法过一遍思路”。得到同意后先用哈希表正常实现再解释异或解法为什么成立把每一步的数学性质讲清楚。这样既能展示你理解了位运算的本质又不会让整道题看起来像“背了一个标准答案”。我最想强调的一点是不要把自己变成一个“背题机器”。LeetCode的高频题本质上就那么多真正的核心竞争力不在于记住多少解法而在于面对新题时能不能快速识别它属于哪个套路、用什么工具去拆解。重复元素这系列题目就是很好的“套路识别训练场”。回头看这几十道题其实真正的收获不是那些精妙的解法和漂亮的时间复杂度而是每次踩坑之后总结出来的“为什么”——为什么这里要用虚拟头节点为什么比较的是slow - 2而不是slow - 1为什么数组可以当链表走。记住这些“为什么”刷题才不会变成背答案。