刷 LeetCode 热题 100 的时候我总习惯把题目分成两类一类是能靠模板的二叉树、链表、动态规划看到题目基本知道往哪个方向想另一类是开窍型的看起来只是一个普通数组但第一次见就是想不到解法。技巧篇这五道题——只出现一次的数字、多数元素、颜色分类、下一个排列、寻找重复数——全属于后者。它们各自用到的异或、摩尔投票、三指针、字典序、Floyd判圈表面是五个毫不相干的知识点底层却共享同一个学习逻辑在很极限的复杂度约束下靠数据自身的数学结构解题而不是靠容器和模板。这篇内容适合正在系统性刷热题 100、准备算法面试或者看完题解后感觉“每个字都认识但串不起来”的同学。我会把每一道题的朴素思路、正解推导、易错边界全拆开讲最后再给一张可以直接复习的对照表。文里的代码风格偏 C但思路部分用任何语言理解都没有障碍。1. 为什么这五道题会在热题100里被单拎出来叫“技巧篇”1.1 它们都没有明显的“数据结构提示”一口气刷到热题100技巧篇的时候第一反应通常是这五道题肉眼可见地跟前面的树、链表、栈不在一个画风。前面的题看到括号就想到栈看到层级结构就想到递归看到链表就想到快慢指针而技巧篇的每题都是一个光秃秃的数组没有任何“容器提示”。比如“只出现一次的数字”和“多数元素”题目里出现的只是若干个整数你甚至不知道该把它们理解成无序数组、可排序序列还是某种位模式集合。“颜色分类”稍微直白一点但它考的不是“排序”而是“原地单趟扫描”。“下一个排列”和“寻找重复数”更狠前者要求理解排列之间的字典序后者连数组本身都不能改。数据结构题的核心是“选对容器”技巧题的核心是“看穿数据底层的数学结构”。这是两条完全不同的思路。我刚开始刷的时候没意识到这一点结果就是每题都能看懂题解但自己独立想就是想不出来因为我在找容器、找模板而这组题根本不给模板。1.2 五种技巧其实只对应三种底层思维把五个题放一起对比之后我总结出三种反复出现的底层思维。第一种是“抵消”。只出现一次的数字用异或成对的数字相互抵消多数元素用摩尔投票不同的数字两两抵消最后剩下的就是答案。它们不依赖排序不依赖统计只依赖“一定存在某种对称性可以被消掉”这个事实。第二种是“维护区间边界”。颜色分类不是真的在排三色而是用三个指针把数组划分成四个连续区域下一个排列也不是让你生成所有排列而是维护“前缀不动、后缀翻转”的字典序边界。这类题的共同特征是答案其实已经藏在一个有序的结构里你要做的只是找到分界点。第三种是“把数组当成图或链表”。寻找重复数表面是一维数组实际上可以把每个下标当成节点、把值当成 next 指针问题瞬间就变成了环检测。这一类需要比较大的思维跳跃也是最典型的“技巧”。建议刷题时别急着记代码先问自己这题的不变量是什么抵消边界还是链结构想明白了代码自己都能推出来。1.3 为什么空间复杂度约束是这组题的灵魂还有一个容易被忽略的因素这五道题里大多数正解都被复杂度约束“逼”出来的。只出现一次的数字要求线性时间、常数空间颜色分类要求一趟扫描寻找重复数不能修改数组、只能用 O(1) 额外空间。如果只是实现功能哈希表能解决一半排序能解决另一半但这组题要的就是“把空间压到常数”。所以我的习惯是看到这类题先圈出复杂度要求再倒推满足条件的算法。空间受限时哈希表淘汰排序的思想淘汰接下来才会想到异或、投票、指针、判圈。这个习惯对我后来做面试题帮助特别大后面每一题我都会再把“复杂度约束如何逼出正解”这个过程过一遍。2. 只出现一次的数字异或运算的“配对抵消”2.1 哈希和排序为什么不完美题目原描述一个非空整数数组除了某个元素只出现一次外其余每个元素都恰好出现两次。找出那个只出现一次的元素。要求线性时间并且最好不用额外空间。最直觉的解法是哈希表遍历一遍统计频次再遍历哈希表找频次为 1 的值。清晰、正确但额外空间是 O(n)在“常数空间”的要求下不满足。排序也可以排完序之后相同的数会相邻但排序本身 O(nlogn)而且很多情况下排序会改变原数组性质不适合。注意题目里的“恰好出现两次”非常关键。它给了很强的对称性如果只看偶数次出现的数它们应该互相抵消。哈希表就像一个记账本什么都要记记的越多越占地方而异或更像一个“自动抵消器”遇到相同的数直接消化掉不需要记账。2.2 异或的思路从哪来异或XOR有三个性质需要记牢a ^ a 0同一个数异或自己等于 0也就是“两个相同数字抵消”a ^ 0 a任何数异或 0 等于自己异或满足交换律和结合律顺序不影响结果把这三个性质连起来如果我把数组里所有元素全部异或一遍由于成对的元素都满足a^a0最终结果等于“出现一次的那个数 ^ 0”也就是它本身。推导过程就是这么几行int singleNumber(vectorint nums) { int ans 0; for (int num : nums) { ans ^ num; } return ans; }我一开始总是担心“遍历顺序会不会影响结果”其实交换律保证不影响。所以这道题的正解简单到有点反常但如果你没意识到异或的存在就会陷入“哈希空间大、排序时间慢”的两难。这里多说一句用这一题面试时可以顺带提“位计数”思路——统计 32 位每一位的出现次数出现奇数次的位就是答案中为 1 的位。这个思路更通用空间只是 32 个计数器写起来比异或长但在某些变体题里非常有用。2.3 一个值得延伸的变体把题目变一下如果数组里有两个数只出现一次其余每个数都出现两次要求找出这两个数。这个变体是对异或理解的最好检验。思路先把所有数异或一遍得到a ^ b它是两个目标数的异或结果一定不为 0。找到a^b里任意一个为 1 的位说明在这一位上 a 和 b 不相同按照这个位把数组分成两组一组是该位为 1 的数一组是该位为 0 的数a 和 b 必然被分到不同组。同组内其他数都成对出现分别做一次异或每组剩下的就是 a 和 b。我建议学完“只出现一次的数字”后顺手把上面这个变体做一遍。它能让你真正理解“异或抵消的不是元素属性而是比特位上的重复特征”这也是这道技巧题最重要的收获。3. 多数元素摩尔投票维护的是“候选人剩余票数”3.1 从排序中位数到 O(n) 抵消多数元素的题目描述也很简单大小为 n 的数组找到一个出现次数大于 n/2 的元素题目保证一定存在。常见的三个思路哈希统计需要 O(n) 空间排序之后直接取中间位置元素因为多数元素出现次数超过一半排序后在中间位置必然还是它但排序是 O(nlogn)。这两个都能做但距离“线性时间常数空间”都差一点。和上一题的“异或抵消”类似多数元素也有一个抵消版解法摩尔投票。它不统计每个数字究竟出现了几次而是维护一个“当前候选人”和一个“净票数”。遍历时如果净票数为 0 就换候选人接下来的数字如果跟候选人相同净票数 1不同则 -1。所有数字都像在搞“同归于尽”因为多数元素占总人数超过一半其他所有元素合起来也没法把所有多数元素的票全部抵消掉最后留下来的候选人必然是多数元素。3.2 用具体例子跑一遍摩尔投票以数组[2,2,1,1,1,2,2]为例n72 出现 4 次是多数元素。从头遍历初始 count 0遇到第一个 2count 为 0所以 candidate2count1遇到第二个 2与 candidate 相同count2遇到第三个元素 1不同count1遇到第四个元素 1不同count0遇到第五个元素 1count 为 0candidate 换成 1count1遇到第六个元素 2不同count0遇到第七个元素 2count 为 0candidate 换成 2count1最终 candidate 是 2。注意中间 candidate 从 2 换成了 1又换回了 2这正是“抵消”过程的体现。多数元素 2 虽然中间一度被 1 抢占过候选人资格但它的数量优势最终会让它重新站到最后。代码int majorityElement(vectorint nums) { int candidate 0; int count 0; for (int num : nums) { if (count 0) { candidate num; } if (num candidate) { count; } else { count--; } } return candidate; }注意代码里第六个元素后 count 已经变成 0所以第七个元素会重新把 candidate 设为 2。逻辑上没问题但我当初写的时候经常把两个 if 合并成 if-else导致 count 为 0 但 candidate 没有被及时更换输出就会出错。建议动手敲一遍。3.3 题目没保证“多数存在”时怎么办摩尔投票有个前提题目保证多数元素一定存在。如果去掉这个前提摩尔投票返回的 candidate 可能是任何元素因为你只是在玩抵消并没有验证最终结果出现次数。所以面试延伸题经常是“数组里不一定存在多数元素找出出现次数大于 n/2 的元素若没有则返回 -1”。做法是两遍扫描第一遍跑摩尔投票得到一个候选人第二遍重新统计该候选人的真实出现次数只有次数大于 n/2 才返回它否则返回 -1。第二遍扫描是很多初学的人漏掉的。我第一遍独立写这个变体时直接把摩尔投票结果当答案交出去结果被问住了。补上验证环节后这个解法才是完整的。4. 颜色分类荷兰国旗问题的三指针边界管理4.1 为什么计数排序在这里不够“漂亮”颜色分类的题目是一个只包含 0、1、2 的数组要求原地排序并按 0、1、2 顺序排列。最笨的方法当然是排序算法但 0、1、2 只有三种值用计数排序更爽先统计 0、1、2 各有多少个再直接重填数组。两趟扫描O(n) 时间和 O(1) 空间看起来已经很好了。但这道题在热题 100 里的标准考法是“只允许一趟常数空间的扫描”意思是你不能在统计完数量之后再重新填一遍必须边扫边交换。计数排序在这一条上就不满足了。这也是“技巧篇”的刁钻之处功能上计数排序已经解决但复杂度被进一步压紧后你需要一个更精巧的原地单趟算法。这个问题有个更古老的名字荷兰国旗问题。把三种颜色分别归位本质上就是在数组里维护三个连续区域。4.2 三个指针的区间语义定义三个指针low、mid、high。循环过程中数组被分成四段[0, low)区域全部是 0已经归位[low, mid)区域全部是 1已经归位(high, n-1]区域全部是 2已经归位[mid, high]区域尚未扫描里面的值是 0、1、2 都未知用一句口诀0 往左送2 往右送1 原地不动。实现代码void sortColors(vectorint nums) { int low 0, mid 0, high nums.size() - 1; while (mid high) { if (nums[mid] 0) { swap(nums[low], nums[mid]); low; mid; } else if (nums[mid] 1) { mid; } else { swap(nums[mid], nums[high]); high--; } } }第一次看懂这段代码的人都会产生同一个疑问为什么遇到 2 交换后不执行 mid遇到 0 交换后反而执行 mid这就要回到区间语义里去解释。4.3 边界最容易错的地方先看遇到 0 的情况。low 指向的位置属于已扫描区间里面只可能有 0 或 1不可能是 2因为 2 一旦被扫到就会被 swap 到 high 去。把这样一个“已知不是 2”的值换到 mid 位置它只用再判断一次 0 还是 1所以交换后 mid 是安全的。再看遇到 2 的情况。nums[high] 来自完全未知的待扫描区域它的值是 0、1、2 中的任何一种。把它换到 mid 之后当前位置并没有被“消费”掉下一次循环必须原样再看一遍。所以交换 2 之后只能 high--不能动 mid。循环终止条件是mid high而不是mid high。如果写成mid high当 mid 走到 high 位置时循环就已经退出但那个位置的值其实还没被扫描和处理大概率会漏掉一个元素。我最初踩过一次这个坑样例[1,0,1,2,1]跑出来差一位排查半天才想起是终止条件的问题。用[2,0,2,1,1,0]手动跑一遍也能验证整个过程 high 不断左移low 不断右移最后数组会稳定地变成[0,0,1,1,2,2]。这道题写顺了之后对快排里的双指针 partition 也理解得更深因为两者本质都是“用指针维护数组区域区域边界就是循环不变量”。5. 下一个排列从右往左找“破坏点”才是关键5.1 字典序的“下一个”叫什么先明确问题给定一个数组例如[1,2,3]要求原地把它改成字典序刚好比它大一号的排列也就是[1,3,2]。如果当前排列已经是最大排列整个排列降序比如[3,2,1]就把它翻转为最小排列[1,2,3]。再比如[1,1,5]的下一个是[1,5,1]因为数字可以重复。字典序类似查英文词典从第一位开始谁的第一位小谁排前面第一位相同就看第二位以此类推。所以一个排列要“变大”最理想的方式是尽量保持左边的高位不变只让右边某一位变大一点然后把右边的部分调整成该前缀下最小的样子。这就是标准解法的逻辑起点。5.2 一步一步推出标准解法标准解法分三步每一步都能用字典序解释。第一步从右往左找到第一个满足nums[i] nums[i1]的位置 i。这个位置就是“破坏点”它右边的部分全是降序排列已经是该后缀能表达的字典序最大值想让整个排列再变大必须动到 i 这个位。如果从头到尾都找不到这样的 i说明整个数组整体降序已经是最大排列直接整体反转即可。第二步在 i 右边的降序段里从右往左找到第一个大于 nums[i] 的元素 nums[j]然后交换 nums[i] 和 nums[j]。为什么从右往左因为右侧是降序越往右越小从右往左碰到的第一个大于 nums[i] 的元素正好是“所有大于 nums[i] 的元素里最小的那个”。让 i 位变成那个最小的大值前缀的增长幅度才最小才能保证是“下一个”而不是“下下个”。第三步把 i1 到数组末尾的区间整体翻转。交换之后右侧仍然是降序但位权更低的这些位置应当取该前缀下的最小区间排列也就是升序。翻转一下正好完成。代码void nextPermutation(vectorint nums) { int n nums.size(); int i n - 2; while (i 0 nums[i] nums[i 1]) i--; if (i 0) { int j n - 1; while (j 0 nums[j] nums[i]) j--; swap(nums[i], nums[j]); } reverse(nums.begin() i 1, nums.end()); }用一个稍微复杂的例子走一遍[1,5,8,4,7,6,5,3,1]。从右往左找第一个满足nums[i] nums[i1]的是 i3因为 nums[3]4 nums[4]7。在右侧降序段[7,6,5,3,1]中从右往左第一个大于 4 的元素是 5交换 4 和 5得到[1,5,8,5,7,6,4,3,1]。再把 i14 到末尾的部分[7,6,4,3,1]翻转成[1,3,4,6,7]最终结果是[1,5,8,5,1,3,4,6,7]它正是[1,5,8,4,7,6,5,3,1]的字典序下一个。5.3 相等元素怎么处理两个比较符号经常被写错。找 i 时要用nums[i] nums[i1]继续左移而不是nums[i] nums[i1]。因为只有严格小于才构成“可以增大的后缀边界”等于的数字之间没有大小差不算破坏点。比如[1,1,1]这种全等数组用会一路滑到 i-1最终整体反转结果还是[1,1,1]完全正确。找 j 时要用nums[j] nums[i]继续左移而不是nums[j] nums[i]。依然因为要找“严格大于 nums[i] 的最小值”等于 nums[i] 的元素不能作为交换对象。如果换成在存在重复元素时可能会选到一个等于 nums[i] 的元素交换后字典序不变结果出错。题目给[1,1,5]就是为了卡这个点标准答案应该是[1,5,1]。另外我会顺便记住一件事标准库的 next_permutation 底层就是这套逻辑。自己实现一遍之后以后再遇到“全排列按序输出”之类的题就不会只会递归回溯了。6. 寻找重复数把数组当链表的 Floyd 判圈法6.1 题目约束为什么把常规方法全堵死寻找重复数的描述n1 个整数所有整数都在 [1, n] 范围内恰好有一个整数重复可以重复多次找出它。限制有三条不能修改原数组、只能用 O(1) 额外空间、时间复杂度优于 O(n²)。这三条几乎把常规思路全堵死了排序法要修改数组直接禁止哈希表是 O(n) 空间不允许双重循环暴力找重复是 O(n²)超时原地标记法把出现过的位置变成负数需要改数组也不行剩下能走的方向其实很少。顺着“值域在 [1,n] 但数组长度是 n1”这个矛盾想会想到鸽巢原理与二分顺着“不能用哈希存状态”想会想到把数组当成某种隐式链表。后者正是这道题真正的“技巧”所在。6.2 从数组构建一条隐式链表把数组里的每个下标都看作一个节点节点的 next 指针就是 nums[i] 的值。也就是说从下标 i 出发下一跳指向下标 nums[i]。因为每个元素的值都在 [1,n]所以从任意一个下标出发下一跳必然落在有效的数组下标范围内不会越界。而 0 这个下标很特殊值域 [1,n] 里没有 0所以没有任何数会指向 00 只能作为链的起点不会出现在环内部。举个经典例子nums [1,3,4,2,2]长度 5n4值域 [1,4]下标 0 指向 nums[0]1下标 1 指向 nums[1]3下标 3 指向 nums[3]2下标 2 指向 nums[2]4下标 4 指向 nums[4]2链就是 0 - 1 - 3 - 2 - 4 - 2 - 4 - 2 ...。重复的 2 同时被下标 3 和下标 4 指向导致节点 2 在这里形成一个环。换句话说重复数值本身正是“环的入口节点”因为只有重复数会被至少两个不同的前置节点指向。6.3 快慢指针相遇后怎么找到环入口Floyd 判圈法大家都熟悉一个快指针一次走两步一个慢指针一次走一步进入环之后两者必然相遇相遇后让一个指针回到起点再以相同速度走最终会在环入口相遇。这条思路在链表题里经常用而寻找重复数就是它最巧妙的变体——链表不是显式给你而是隐藏在数组下标和值的映射里。代码int findDuplicate(vectorint nums) { int slow nums[0]; int 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; }注意快指针那行是fast nums[nums[fast]]不是fast nums[fast]之后再nums[fast]这种写法嵌套求值恰好完成两步移动。第一次写的时候我很容易把 fast 写成nums[slow * 2]之类的错法直接越界后来老实按“每一步都走 nums[下标]”来理解就顺了。为什么相遇后还要从头走一次因为相遇点不一定是环入口。数学关系是从起点到环入口的距离 a等于相遇点在环内绕若干圈后再到入口的距离。所以让一个指针从起点出发、另一个从相遇点出发都每次走一步两者必然同时到达环入口。这里不需要背结论记住“相遇不是为了找到入口而是建立第二个起点”就够用了。6.4 保底思路值域二分如果面试时一时想不到 Floyd 判圈还有一个更稳的保底方案值域二分。因为所有数字都在 [1,n] 内设区间 [low, high] 表示可能的答案范围。每次取 mid统计数组里有多少个元素 mid记为 cnt。如果 cnt mid说明 [1, mid] 这个值域范围内的“位置”少于实际落入该范围的数字个数根据鸽巢原理重复数必然落在这一半否则重复数在 [mid1, high] 这一半。int findDuplicate(vectorint nums) { int n nums.size() - 1; int l 1, r n; while (l r) { int mid l (r - l) / 2; int cnt 0; for (int x : nums) { if (x mid) cnt; } if (cnt mid) r mid; else l mid 1; } return l; }这个解法是 O(nlogn)时间不如 Floyd 判圈但它的优点是逻辑非常直观不容易写错。面试时可以先用它保底再提出 Floyd 判圈作为进阶优化。7. 五道题合在一起对照表与我的刷题心得7.1 一张表把五道题串起来把五个题放在同一张表里复习的时候扫一眼就够题目核心技巧时间复杂度额外空间底层不变量只出现一次的数字异或O(n)O(1)成对数字比特位抵消多数元素摩尔投票O(n)O(1)超过半数的元素抵消不掉颜色分类三指针荷兰国旗O(n)O(1)三个连续区间边界成立下一个排列字典序分界点O(n)O(1)降序后缀可被翻转寻找重复数Floyd 判圈O(n)O(1)重复值等于环入口这张表里最值得关注的是“底层不变量”一列。五个题之所以被归进技巧篇不是因为它们共享某种数据结构而是因为它们都在利用数据自身的规律做主异或的对称性、过半数量的不可抵消性、区间边界的循环不变量、字典序的降序后缀、数组值与下标构成的环。抓住这一列才是真正的“技巧”。7.2 刷这类题最值得养成的三个习惯第一先圈复杂度约束再决定方向。我现在的刷题流程是看完题目先写下两行字——“时间不能超过多少空间能不能用额外数组数组能不能改”。寻找重复数如果没看到“不能修改数组”很可能会直接往原地标记走看到之后思路会自然收敛到二分或判圈。第二遇到“一眼看不出数据结构”的数组题试着把值当作指针。这不是万能钥匙但在寻找重复数这类“值域与下标重合”的问题里非常有效。遇到类似场景可以问自己如果当前值是下一个下标这条路会不会形成环第三写代码前先手动模拟一个小例子。颜色分类、下一个排列、Floyd 判圈这三道题都非常适合用长度 5 到 7 的小数组在纸上推一遍。我几乎每次都能在推演过程中发现边界问题比直接写完再调试快得多。7.3 关于复习节奏的个人建议我自己的复习节奏是第一天理解并独立默写五段代码第三天不看笔记重新推一遍思路只看题目把解法推出来一周后再把每道题用第二种思路做一次。比如只出现一次的数字用位计数做多数元素用排序中位数验证寻找重复数用值域二分跑一遍。这个过程不是重复劳动而是把“背下来的代码”变成“能生产的思维”。说句实话这五道题我第一次刷的时候每一道都是看了题解才会。但隔一段时间回来重做发现思路开始自己会长出来看到成对出现会想抵消看到值域加长度差一会想鸽巢或判圈看到只允许一次扫描会想维护区间。如果你也正卡在这组题上别急着往下刷先拿纸笔画一画把每个题的“不变量”写出来再回来看这篇效果会完全不一样。