刷 LeetCode 的都知道删除有序数组中的重复项是个系列题26 题是入门80 题是进阶中间就多了一个“每个元素最多出现两次”的限制。但恰恰是这一个限制让很多人的第一版代码从“能过”变成“越写越乱”甚至开始怀疑自己是不是理解错了题意。这篇文章我用 C 语言把 80 题从头到尾拆开讲清楚包括双指针是怎么一步步推出来的、两种主流写法各自好在哪以及跟 26 题的对比到底差在哪。无论你是刚刷完 26 题准备进阶还是 C 语言基础不太扎实想借算法题巩固指针操作这篇都适合你慢慢看。1. 先把题目要求拆到不能再拆1.1 四个隐藏条件决定了解法方向题目给的描述很短给你一个有序数组原地删除重复出现的元素让每个元素最多出现两次返回删除后数组的新长度。很多人盯着“重复”“删除”“返回长度”这三个词就开始动手了结果一做就错。原因在于题目里还藏着四个不显眼的硬条件它们才是决定解法方向的真正关键。第一个条件是“有序”。数组是有序的这意味着所有相等的元素一定紧紧挨在一起。这个性质非常重要它直接决定了我们只需要一趟从左到右的扫描就能把重复情况全部看完不需要回头看已经走过的元素。第二个条件是“原地修改”。你不能开一个新数组把筛选后的结果拷贝进去再赋回来。题目要求你在原数组上直接改空间复杂度必须做到 O(1)。这就排除了“哈希表统计 重建数组”这条路也排除了很多新手的偷懒写法。第三个条件是“每个元素最多出现两次”不是一次。这是跟 26 题最本质的区别。26 题里只要遇到跟前面一样的就丢掉保留一个80 题里前两个相同的值得保留第三个及以后的重复值才需要丢掉。很多人在这一步翻车把 80 题当 26 题做最后只保留了一个。第四个条件是关于返回值的用法也是面试官最喜欢追问的细节返回的新长度 n 之后调用方只会看数组的前 n 个位置且这前 n 个位置必须是你整理好的结果。也就是说你不仅要返回一个数字还要真的把数组前 n 位改对。后面位置的残留数据无所谓因为调用方不会看。1.2 为什么这道题值得认真做两遍从题目难度看80 题只算中等但它的价值不在“难”而在“典型”。它几乎是双指针技巧里最干净利落的一道题一个指针负责读一个指针负责写中间通过一个计数变量来控制“最多保留两个”的规则。这个套路一旦掌握你会发现在数组类题目里非常吃得开比如移除元素、移动零、合并有序数组甚至更复杂的滑动窗口问题底层都是同一套思想。另外这道题对 C 语言初学者来说还有一个额外收获它能逼你搞清楚“数组下标”和“实际长度”的区别。很多初学者写循环时习惯用 i 表示下标用 n 表示长度但遇到 write、read 这类双指针变量时经常会混淆“下一个写入位置”和“已写入元素的个数”。80 题里这两个概念几乎贴在脸上你把这道题吃透后面再写 memmove、手写字符串处理这类代码心里会踏实很多。我个人的建议是不要只满足于把代码写对然后把答案背下来。你最好能做到三件事第一不看答案自己推一遍思路第二把两种主流写法都写一遍第三想清楚为什么这两种写法本质上是同一件事。下面我就按这个顺序来展开。2. 思路演进从“暴力搬移”到“双指针”2.1 最直觉的做法错在哪大部分人的第一反应是用一个新数组遍历原数组发现当前元素已经出现两次了就跳过否则拷进去。这个方法思路没错但坏就坏在它不满足“原地”。你一旦新建数组空间复杂度就变成 O(n)面试的时候大概率会被追问“能不能原地做”。那原地做是不是可以边遍历边删比如用 for 循环扫数组发现第三个相同值就调用一下 memmove 把后面所有元素往前搬一格。这个方案确实原地但它有两个问题。第一每删一个元素后面所有元素都要移动一次最坏情况下是 O(n²)数组一长就超时。第二用 C 语言做删除操作时数组长度会变for 循环里如果还按原长度遍历很容易越界或者漏看元素这是个非常隐蔽的坑。我见过不少新手在这里绕圈子删掉一个元素后数组变短了下一个重复值的位置也跟着变如果还按原来的 i 去走就会跳过元素最后得到错误答案。这种“一边删一边改下标”的写法本质上是把动态变化的问题用固定思维去解不乱才怪。2.2 双指针的本质慢指针盖章快指针巡逻既然不能麻烦地搬来搬去那能不能换个思路我们不是真的“删除”元素而是“覆盖”元素既然是覆盖就不需要把后面所有元素搬一遍只需要把应该保留的值往前挪到合适的位置就行。这就要引入两个指针。一个叫 read用来从头到尾扫描原数组它就像巡逻员负责“看看当前这个值能不能留下”另一个叫 write指向当前数组中“下一个可以覆盖的位置”它就像盖章员负责把 read 带回来的有效值写到正确的位置。write 往前走得慢read 往前走得快所以这种写法叫快慢指针也叫双指针。它的精妙之处在于read 永远走在 write 前面read 读过的位置write 才有可能会写上新的值read 还没读到的区域write 绝对不会碰。这样就不会出现“把还没处理的原始数据覆盖掉”的灾难。用生活化的比喻来说就是一条传送带上送来一堆货物read 负责检查每个货物是否合格write 负责把合格的货物摆到前面货架上。搬运过程中write 不会跑到传送带还没送到的区域去摆货所以安全得很。2.3 和 26 题的差别就藏在一个词里如果你已经刷过 26 题你会发现两题的框架几乎一模一样。26 题里判定“能不能保留”的条件是当前读到的值是否跟 write 指向的前一个值相同如果不同就保留。这里隐含了一个规则每个值最多只能有一个出现在结果里。80 题改了一个词最多有两个。那么这个“最多有一个”到“最多有两个”的变化在代码上该怎么体现两种最常见的思路从这里分岔。第一种思路是给每个“当前值”配一个计数器 count记录它在结果里已经被保留了几次。count 为 1 或 2 都允许写入count 到 3 就跳过。这种写法直观、好理解也容易扩展。第二种思路是放弃计数直接利用“有序数组 最多保留两个”的数学性质如果当前 read 读到的值跟结果序列里倒数第二个位置的值相等那说明结果里已经有至少两个当前值了再多一个就超过两个所以跳过反之则可以写入。这就是很多人说的“跟 write - 2 比较”的写法代码极短但需要先想明白为什么它是对的。这两种思路对应下面两套完整实现。3. C 语言完整实现两种写法逐行讲透3.1 方案一带计数器的快慢指针先看最直观、最好理解的计数器版本。我把完整代码贴出来然后逐行解释。int removeDuplicates(int* nums, int numsSize) { if (numsSize 2) { return numsSize; } int write 1; // 慢指针下一个可写入的位置前两个元素肯定保留 int count 1; // 当前值在结果中已保留的次数 for (int read 1; read numsSize; read) { if (nums[read] nums[read - 1]) { count; } else { count 1; } if (count 2) { nums[write] nums[read]; write; } } return write; }第一行先处理短数组。数组长度小于 2 时不管里面是什么都不可能出现“同一个值超过两个”的情况所以直接返回原长度。这里用numsSize 2而不是numsSize 0是因为长度为 1 时也不需要处理写小于 2 就把两种情况一起覆盖了少写一个分支。然后初始化两个变量。write 1表示数组前两个位置下标 0 和 1至少可以容纳前两个元素所以从下标 1 开始作为写入点。count 1表示第一个元素已经保留了一个。循环从read 1开始因为下标 0 已经在结果里了不需要再处理。循环体内先判断当前元素和上一个元素是否相等。相等说明是同一个值的延续count 加一不相等说明遇见新值count 重置为 1。判断完 count 后只要 count 小于等于 2就把当前值写到 write 指向的位置然后 write 前进一格。这里容易踩的坑是nums[read]和nums[read - 1]的比较用的是原数组相邻元素比较而不是和结果序列比较。因为 write 永远小于等于 readnums[read]这个位置的数据还没有被 write 覆盖过所以它始终是原始数据比较结果一定可靠。这一点在调试时很容易被人忽略很多人排查半天最后才发现是自己担心多了。用[1, 1, 1, 2, 2, 3]走一遍这个过程read 到下标 2 时count 变成 3因为 3 大于 2所以第三个 1 被跳过read 到下标 3 时值是 2和前面的 1 不同count 重置为 1于是写入read 到下标 4 时值还是 2count 变成 2写入read 到下标 5 时值是 3count 重置为 1写入。最终 write 停在 5返回 5数组前五位变成[1, 1, 2, 2, 3]完全正确。这个写法的好处是逻辑非常清楚面试时讲思路也流畅。坏处是变量多一个 count代码稍微长一点但代价可以忽略我建议新手第一遍先掌握这个。3.2 方案二向前看两位的精简写法第二种写法在 LeetCode 讨论区非常流行因为它短。完整代码如下。int removeDuplicates(int* nums, int numsSize) { if (numsSize 2) { return numsSize; } int write 2; for (int read 2; read numsSize; read) { if (nums[read] ! nums[write - 2]) { nums[write] nums[read]; write; } } return write; }这个写法看起来像变魔术没有 count也没有对“上一个值”的判断直接用nums[read]和nums[write - 2]比。为什么这样就能保证“每个值最多两个”关键在于write - 2的语义。write是结果数组“下一个可写入的位置”所以write - 1是结果数组的最后一个元素write - 2是结果数组的倒数第二个元素。当nums[read]和nums[write - 2]相等时说明结果数组里已经有至少两个和当前值相同的元素了一个在 write - 2一个在 write - 1再加上当前这个就是第三个不能要。反过来如果不等那就说明当前值在结果数组里出现得还不够两次至少是安全的可以写入。有人可能会疑惑万一结果数组里只有一个当前值而write - 2并不是当前值那岂不就误放行了这就是有序数组的功劳。数组有序相等的值永远连续出现而结果数组里相同值的数量不可能超过两个所以如果当前值在结果里已经有一个它必然位于 write - 1 位置此时 write - 2 是上一个不同的值两者不相等条件成立允许第二次出现。如果当前值在结果里已经有两个它们必然占据 write - 2 和 write - 1 两个位置此时比较结果相等拒绝第三次出现。两种情况正好覆盖既不会多放也不会漏放。用同样的测试用例走一遍[1, 1, 1, 2, 2, 3]write 初始为 2。read 在 2 时nums[2] 1nums[write - 2] nums[0] 1相等跳过。read 在 3 时nums[3] 2nums[write - 2] nums[0] 1不等写入write 变 3。read 在 4 时nums[4] 2nums[write - 2] nums[1] 1不等写入write 变 4。read 在 5 时nums[5] 3nums[write - 2] nums[2]注意此刻 nums[2] 已经被覆盖成 23 和 2 不等写入write 变 5。返回 5。一切正确。这个写法唯一的心理门槛是你看到nums[write - 2]可能已经被覆盖过心里会不踏实。但仔细想想write 永远比 read 小write - 2这个位置一定已经被处理过它的值就是当前结果序列倒数第二个位置的值完全可靠。想通这一点这个写法就很香了。3.3 两个方案的取舍对比我把两种写法放在一张表里对比方便你按自己的习惯选。对比维度计数器版本向前看两位版本核心变量write countwrite 一个变量判断逻辑统计当前值出现次数count 2 才写和结果倒数第二个位置比较不等才写代码长度稍长约 15 行精简约 10 行可读性高适合新手理解中等需要先理解 write - 2 的含义扩展性改成“最多保留 k 个”需要改一个数改成“最多保留 k 个”也只需改一个数出错风险count 忘记重置是重灾区write - 2 比较语义想不通容易写错我个人的建议是第一次写用计数器版本因为它跟我们的直觉一致写错了也容易定位写熟之后把向前看两位的版本也吃透因为它在面试时更简洁而且能体现你对数组特性的理解深度。两个版本都掌握了这道题才算真正过关。4. 与第 26 题深度对比一通百通4.1 26 题的标准答案长什么样在讲 80 题和 26 题的关系之前先把 26 题的标准代码摆出来这样对比才有锚点。26 题要求每个元素只保留一个经典的快慢指针写法是这样的。int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) { return 0; } int write 1; for (int read 1; read numsSize; read) { if (nums[read] ! nums[write - 1]) { nums[write] nums[read]; write; } } return write; }注意这里的判断条件nums[read]和nums[write - 1]比较。write - 1 是结果数组的最后一个元素如果两者不等说明这是个新值写入后 write 前进。整个过程没有计数因为 26 题的规则就是“每个值只保留一个”只要发现当前值跟结果最后一个值不同就一定可以写入。这里有个重要的思维习惯你可以把 26 题的判断条件理解为“跟结果数组的最后一个位置比较”而不是“跟原数组上一个位置比较”。虽然很多实现里两个写法的效果相同但前者才能真正跟 80 题统一起来。4.2 从 26 到 80 的迁移只改了一个数字现在把两个题的关键对比放在一张表里。对比维度第 26 题第 80 题每个元素保留次数最多 1 次最多 2 次比较基准结果数组最后一个元素即 write - 1结果数组倒数第二个元素即 write - 2初始 write 值12需要处理空数组吗需要numsSize 0 时返回 0需要但可以统一写成 numsSize 2 返回 numsSize核心难点理解快慢指针的覆盖写理解“最多两个”如何体现在比较距离上从表里可以看得很清楚26 题就是“跟前面一个比较”80 题就是“跟前面两个比较”。如果把“最大保留数”记为 k那么 26 题的 k 是 180 题的 k 是 2。代码结构上只要把write - 1改成write - 2把初始 write 从 1 改成 2就完成了从 26 到 80 的迁移。所以我说这两道题本质上是一个题。你理解 26 题的快慢指针就应该能推出 80 题你理解了 80 题回头再看 26 题会觉得它只是 k 1 的特例。4.3 再进一步通用模板允许保留 K 个重复既然 k 1 和 k 2 都能用同一个结构解决那干脆直接写一个通用版本允许保留任意 k 个重复。这既是一个很好的思维延伸也是面试时展示能力的加分项。int removeDuplicatesK(int* nums, int numsSize, int k) { if (numsSize k) { return numsSize; } int write k; for (int read k; read numsSize; read) { if (nums[read] ! nums[write - k]) { nums[write] nums[read]; write; } } return write; }当 k 1 时这个函数就是 26 题的实现当 k 2 时它就是 80 题的实现。判断条件nums[read] ! nums[write - k]的语义是看当前值是否和结果序列中从后往前第 k 个元素相等。如果相等说明结果中至少已经有 k 个当前值再加就超了如果不相等说明当前值出现的次数还不足 k 次可以写入。这个模板非常值得背下来。因为 LeetCode 上有一类“删掉重复项”的变种题本质上都是调这个 k 值。你掌握了模板再遇到“最多保留三次”“最多保留四次”的变形就只需要改一个参数根本不需要重新想思路。面试官看到你能把一个具体题目抽象成通用解法通常会认为你对问题本质有理解而不是只会背题。5. 边界条件、测试用例与复杂度分析5.1 边界条件速查表写暴力解法时容易出错写双指针解法时同样要小心边界。我整理了五个最容易出问题的输入场景以及对应的预期输出。输入数组预期输出长度数组前 n 位结果说明[]0[]空数组直接返回 0[1]1[1]单个元素不用处理[1, 1, 1, 1]2[1, 1]全部相同只保留两个[1, 2, 3, 4]4[1, 2, 3, 4]本来就没有重复原样返回[1, 1, 2, 2, 3, 3]6原数组不变每个值恰好出现两次全部保留这张表可以用来快速验证你的代码是否正确。我刷题时的习惯是先跑题目给的示例再跑这几个边界用例全部通过才提交。边界用例几乎能覆盖百分之八十的隐藏错误。5.2 手动模拟一遍完整流程为了彻底看清双指针的运行过程我们用一个稍微复杂一点的例子来手动模拟[1, 1, 1, 2, 2, 3, 3, 3]预期输出长度是 6结果为[1, 1, 2, 2, 3, 3]。用计数器版本的逻辑read 下标nums[read]count是否写入write 变化112写入1 - 2213跳过2321写入2 - 3422写入3 - 4531写入4 - 5632写入5 - 6733跳过6最后 write 停在 6返回 6。注意一个细节write 变量的值刚好就是最终结果数组的长度因为它每写入一次就加一而写入次数就是保留的元素个数。再模拟一下向前看两位版本的同类数据。初始 write 2read 从 2 开始。read 在 2 时nums[2] 1nums[0] 1相等跳过read 在 3 时nums[3] 2nums[write - 2] nums[0] 1不等写入write 变 3read 在 4 时nums[4] 2nums[write - 2] nums[1] 1不等写入write 变 4read 在 5 时nums[5] 3nums[write - 2] nums[2]此时 nums[2] 已被覆盖为 23 和 2 不等写入write 变 5read 在 6 时nums[6] 3nums[write - 2] nums[3]nums[3] 是 23 和 2 不等写入write 变 6read 在 7 时nums[7] 3nums[write - 2] nums[4]此时 nums[4] 是 33 和 3 相等跳过。最终 write 也是 6。两个版本殊途同归。5.3 复杂度分析为什么 O(n) 已经是最优时间上数组从头到尾只扫了一遍每个元素最多被 read 看一次所以时间复杂度是 O(n)。空间上只用了 write、read、count 三四个整型变量没有申请额外数组所以空间复杂度是 O(1)。这两个指标对这道题来说已经是最优。有人可能会问数组有序能不能用二分查找或者更快的办法跳过一大段重复元素理论上可以但实际没意义因为你最终还是要一个个把元素搬到前面来除非重复段极长否则分段的收益很小反而增加代码复杂度。LeetCode 的判题数据也不会因为你用了花哨的跳跃而给出额外分稳妥的 O(n) 双指针就是标准答案。另外C 语言版本还有一个隐性问题numsSize的类型是 int当数组长度为 1 时numsSize 2会直接返回 1这个分支把长度 0、1、2 全部处理掉了避免了 write 初始值超出数组边界的风险。这种“先用边界条件截断”的写法在 C 语言里特别重要因为 C 不会帮你检查数组越界一旦 write 从 2 开始但数组长只有 1你后面必然访问越界结果不可预测。6. 实践中踩过的坑与排查方法6.1 高频错误自查表我刷这道题时踩过坑也看过不少人在评论区贴过自己的错误代码大约有五个错误出现频率最高几乎覆盖了所有提交失败的情况。错误类型错误代码示例后果没处理短数组直接int write 2就开循环数组长度小于 2 时越界访问判断条件用错写成nums[read] ! nums[read - 1]会保留三个相同值count 忘记重置只在相等时加一不等时没重置新值的计数延续旧值误判指针语义混淆把 write 当成已写入元素个数返回 write - 1返回值比实际长度小 1循环边界错误read 从 0 开始write 也从 0 开始第一个元素被跳过或重复写入先说第一个错误。如果你用向前看两位的写法一定要先判断numsSize 2直接返回。否则数组只有两个元素时write 2循环虽然没有进入但后面的代码如果还想访问 nums[write - 2]就会读到一个不存在的下标。很多人在 LeetCode 上报出奇怪的运行时错误回去一查就是这里漏了判断。第三个错误很隐蔽。计数器版本里你要保证“遇到不同值时重置 count 1”这个动作要和“读取新元素”同步。如果忘了重置连续三个 1 之后出现一个 2count 还停留在 3那么 2 会被误判为“已经出现过三次”直接被跳过结果丢失一个 2。这种错误不会让程序崩溃但会让结果悄无声息地少元素最危险。第四个错误主要出现在返回值上。write 的含义是“下一个可写入的位置”它同时就是结果数组的长度。很多人在循环结束后习惯性地返回 write - 1因为“最后一个元素的下标 1”才是长度。但 write 本身已经是从 0 开始计数后的长度你减一反而少了一个。举个最简单的例子原始数组是[1, 2]没有重复循环结束后 write 2返回 2 才是正确答案返回 1 就错了。6.2 现场排查的四个步骤我自己在调试这类双指针题目时有一套固定流程比瞎打 printf 高效得多分享给你。第一步先跑题目自带示例。LeetCode 每个题都有示例第一个示例通常是精心设计的包含各种小陷阱。比如 80 题的示例是[1, 1, 1, 2, 2, 3]它同时包含了“连续三个 1”和“恰好两个 2”足够暴露大部分问题。第二步跑一遍你自己构造的边界用例。我的固定组合是空数组、单个元素、两个相同元素、两个不同元素、全部相同的最长数组。这些用例代码量小你可以心算结果一旦不对劲马上能定位。第三步在循环里打印关键变量。具体来说每一轮输出 read、write、count 三个值再输出当前数组的整体状态。拿计数器版本来说你可以在每次循环结束时打印看看 write 增长的位置是否符合预期。for (int read 1; read numsSize; read) { // ... 原有逻辑 printf(read%d write%d count%d\n, read, write, count); for (int i 0; i numsSize; i) { printf(%d , nums[i]); } printf(\n); }看到实际输出后大多数错误会一目了然。比如 count 没有重置你会看到某个 read 明明是新值count 却还在高位比如 write 增长慢了你会看到数组有效部分缺失元素。第四步对比两个版本的代码。如果你有计数器版本和向前看两位版本用同一个测试用例分别跑一遍结果应该完全一致。如果一边正确一边错误那错误通常出在“比较基准”上回去检查是 write - 1 还是 write - 2 就会发现问题。这个方法让我省了很多排查时间也帮助我真正理解了两种写法的等价性。最后分享一个我后来的刷题习惯把 26 题、80 题和 27 题移除元素放在同一天刷。27 题是不看重复规则的直接移除特定值用的也是快慢指针26 题是每个值留一个80 题是每个值留两个。三题放在一起你会发现它们骨架完全一致只是判定条件换一下。这种成组刷题的方式比单独刷十道互不相关的题更能锻炼“识别题目模式”的能力。等你见多了看到“有序数组 原地去重 最多保留 k 个”这个组合基本不用想就能写出通用模板那才是真的把这一类型题吃透了。
LeetCode 80题：C语言双指针删除有序数组重复项详解
刷 LeetCode 的都知道删除有序数组中的重复项是个系列题26 题是入门80 题是进阶中间就多了一个“每个元素最多出现两次”的限制。但恰恰是这一个限制让很多人的第一版代码从“能过”变成“越写越乱”甚至开始怀疑自己是不是理解错了题意。这篇文章我用 C 语言把 80 题从头到尾拆开讲清楚包括双指针是怎么一步步推出来的、两种主流写法各自好在哪以及跟 26 题的对比到底差在哪。无论你是刚刷完 26 题准备进阶还是 C 语言基础不太扎实想借算法题巩固指针操作这篇都适合你慢慢看。1. 先把题目要求拆到不能再拆1.1 四个隐藏条件决定了解法方向题目给的描述很短给你一个有序数组原地删除重复出现的元素让每个元素最多出现两次返回删除后数组的新长度。很多人盯着“重复”“删除”“返回长度”这三个词就开始动手了结果一做就错。原因在于题目里还藏着四个不显眼的硬条件它们才是决定解法方向的真正关键。第一个条件是“有序”。数组是有序的这意味着所有相等的元素一定紧紧挨在一起。这个性质非常重要它直接决定了我们只需要一趟从左到右的扫描就能把重复情况全部看完不需要回头看已经走过的元素。第二个条件是“原地修改”。你不能开一个新数组把筛选后的结果拷贝进去再赋回来。题目要求你在原数组上直接改空间复杂度必须做到 O(1)。这就排除了“哈希表统计 重建数组”这条路也排除了很多新手的偷懒写法。第三个条件是“每个元素最多出现两次”不是一次。这是跟 26 题最本质的区别。26 题里只要遇到跟前面一样的就丢掉保留一个80 题里前两个相同的值得保留第三个及以后的重复值才需要丢掉。很多人在这一步翻车把 80 题当 26 题做最后只保留了一个。第四个条件是关于返回值的用法也是面试官最喜欢追问的细节返回的新长度 n 之后调用方只会看数组的前 n 个位置且这前 n 个位置必须是你整理好的结果。也就是说你不仅要返回一个数字还要真的把数组前 n 位改对。后面位置的残留数据无所谓因为调用方不会看。1.2 为什么这道题值得认真做两遍从题目难度看80 题只算中等但它的价值不在“难”而在“典型”。它几乎是双指针技巧里最干净利落的一道题一个指针负责读一个指针负责写中间通过一个计数变量来控制“最多保留两个”的规则。这个套路一旦掌握你会发现在数组类题目里非常吃得开比如移除元素、移动零、合并有序数组甚至更复杂的滑动窗口问题底层都是同一套思想。另外这道题对 C 语言初学者来说还有一个额外收获它能逼你搞清楚“数组下标”和“实际长度”的区别。很多初学者写循环时习惯用 i 表示下标用 n 表示长度但遇到 write、read 这类双指针变量时经常会混淆“下一个写入位置”和“已写入元素的个数”。80 题里这两个概念几乎贴在脸上你把这道题吃透后面再写 memmove、手写字符串处理这类代码心里会踏实很多。我个人的建议是不要只满足于把代码写对然后把答案背下来。你最好能做到三件事第一不看答案自己推一遍思路第二把两种主流写法都写一遍第三想清楚为什么这两种写法本质上是同一件事。下面我就按这个顺序来展开。2. 思路演进从“暴力搬移”到“双指针”2.1 最直觉的做法错在哪大部分人的第一反应是用一个新数组遍历原数组发现当前元素已经出现两次了就跳过否则拷进去。这个方法思路没错但坏就坏在它不满足“原地”。你一旦新建数组空间复杂度就变成 O(n)面试的时候大概率会被追问“能不能原地做”。那原地做是不是可以边遍历边删比如用 for 循环扫数组发现第三个相同值就调用一下 memmove 把后面所有元素往前搬一格。这个方案确实原地但它有两个问题。第一每删一个元素后面所有元素都要移动一次最坏情况下是 O(n²)数组一长就超时。第二用 C 语言做删除操作时数组长度会变for 循环里如果还按原长度遍历很容易越界或者漏看元素这是个非常隐蔽的坑。我见过不少新手在这里绕圈子删掉一个元素后数组变短了下一个重复值的位置也跟着变如果还按原来的 i 去走就会跳过元素最后得到错误答案。这种“一边删一边改下标”的写法本质上是把动态变化的问题用固定思维去解不乱才怪。2.2 双指针的本质慢指针盖章快指针巡逻既然不能麻烦地搬来搬去那能不能换个思路我们不是真的“删除”元素而是“覆盖”元素既然是覆盖就不需要把后面所有元素搬一遍只需要把应该保留的值往前挪到合适的位置就行。这就要引入两个指针。一个叫 read用来从头到尾扫描原数组它就像巡逻员负责“看看当前这个值能不能留下”另一个叫 write指向当前数组中“下一个可以覆盖的位置”它就像盖章员负责把 read 带回来的有效值写到正确的位置。write 往前走得慢read 往前走得快所以这种写法叫快慢指针也叫双指针。它的精妙之处在于read 永远走在 write 前面read 读过的位置write 才有可能会写上新的值read 还没读到的区域write 绝对不会碰。这样就不会出现“把还没处理的原始数据覆盖掉”的灾难。用生活化的比喻来说就是一条传送带上送来一堆货物read 负责检查每个货物是否合格write 负责把合格的货物摆到前面货架上。搬运过程中write 不会跑到传送带还没送到的区域去摆货所以安全得很。2.3 和 26 题的差别就藏在一个词里如果你已经刷过 26 题你会发现两题的框架几乎一模一样。26 题里判定“能不能保留”的条件是当前读到的值是否跟 write 指向的前一个值相同如果不同就保留。这里隐含了一个规则每个值最多只能有一个出现在结果里。80 题改了一个词最多有两个。那么这个“最多有一个”到“最多有两个”的变化在代码上该怎么体现两种最常见的思路从这里分岔。第一种思路是给每个“当前值”配一个计数器 count记录它在结果里已经被保留了几次。count 为 1 或 2 都允许写入count 到 3 就跳过。这种写法直观、好理解也容易扩展。第二种思路是放弃计数直接利用“有序数组 最多保留两个”的数学性质如果当前 read 读到的值跟结果序列里倒数第二个位置的值相等那说明结果里已经有至少两个当前值了再多一个就超过两个所以跳过反之则可以写入。这就是很多人说的“跟 write - 2 比较”的写法代码极短但需要先想明白为什么它是对的。这两种思路对应下面两套完整实现。3. C 语言完整实现两种写法逐行讲透3.1 方案一带计数器的快慢指针先看最直观、最好理解的计数器版本。我把完整代码贴出来然后逐行解释。int removeDuplicates(int* nums, int numsSize) { if (numsSize 2) { return numsSize; } int write 1; // 慢指针下一个可写入的位置前两个元素肯定保留 int count 1; // 当前值在结果中已保留的次数 for (int read 1; read numsSize; read) { if (nums[read] nums[read - 1]) { count; } else { count 1; } if (count 2) { nums[write] nums[read]; write; } } return write; }第一行先处理短数组。数组长度小于 2 时不管里面是什么都不可能出现“同一个值超过两个”的情况所以直接返回原长度。这里用numsSize 2而不是numsSize 0是因为长度为 1 时也不需要处理写小于 2 就把两种情况一起覆盖了少写一个分支。然后初始化两个变量。write 1表示数组前两个位置下标 0 和 1至少可以容纳前两个元素所以从下标 1 开始作为写入点。count 1表示第一个元素已经保留了一个。循环从read 1开始因为下标 0 已经在结果里了不需要再处理。循环体内先判断当前元素和上一个元素是否相等。相等说明是同一个值的延续count 加一不相等说明遇见新值count 重置为 1。判断完 count 后只要 count 小于等于 2就把当前值写到 write 指向的位置然后 write 前进一格。这里容易踩的坑是nums[read]和nums[read - 1]的比较用的是原数组相邻元素比较而不是和结果序列比较。因为 write 永远小于等于 readnums[read]这个位置的数据还没有被 write 覆盖过所以它始终是原始数据比较结果一定可靠。这一点在调试时很容易被人忽略很多人排查半天最后才发现是自己担心多了。用[1, 1, 1, 2, 2, 3]走一遍这个过程read 到下标 2 时count 变成 3因为 3 大于 2所以第三个 1 被跳过read 到下标 3 时值是 2和前面的 1 不同count 重置为 1于是写入read 到下标 4 时值还是 2count 变成 2写入read 到下标 5 时值是 3count 重置为 1写入。最终 write 停在 5返回 5数组前五位变成[1, 1, 2, 2, 3]完全正确。这个写法的好处是逻辑非常清楚面试时讲思路也流畅。坏处是变量多一个 count代码稍微长一点但代价可以忽略我建议新手第一遍先掌握这个。3.2 方案二向前看两位的精简写法第二种写法在 LeetCode 讨论区非常流行因为它短。完整代码如下。int removeDuplicates(int* nums, int numsSize) { if (numsSize 2) { return numsSize; } int write 2; for (int read 2; read numsSize; read) { if (nums[read] ! nums[write - 2]) { nums[write] nums[read]; write; } } return write; }这个写法看起来像变魔术没有 count也没有对“上一个值”的判断直接用nums[read]和nums[write - 2]比。为什么这样就能保证“每个值最多两个”关键在于write - 2的语义。write是结果数组“下一个可写入的位置”所以write - 1是结果数组的最后一个元素write - 2是结果数组的倒数第二个元素。当nums[read]和nums[write - 2]相等时说明结果数组里已经有至少两个和当前值相同的元素了一个在 write - 2一个在 write - 1再加上当前这个就是第三个不能要。反过来如果不等那就说明当前值在结果数组里出现得还不够两次至少是安全的可以写入。有人可能会疑惑万一结果数组里只有一个当前值而write - 2并不是当前值那岂不就误放行了这就是有序数组的功劳。数组有序相等的值永远连续出现而结果数组里相同值的数量不可能超过两个所以如果当前值在结果里已经有一个它必然位于 write - 1 位置此时 write - 2 是上一个不同的值两者不相等条件成立允许第二次出现。如果当前值在结果里已经有两个它们必然占据 write - 2 和 write - 1 两个位置此时比较结果相等拒绝第三次出现。两种情况正好覆盖既不会多放也不会漏放。用同样的测试用例走一遍[1, 1, 1, 2, 2, 3]write 初始为 2。read 在 2 时nums[2] 1nums[write - 2] nums[0] 1相等跳过。read 在 3 时nums[3] 2nums[write - 2] nums[0] 1不等写入write 变 3。read 在 4 时nums[4] 2nums[write - 2] nums[1] 1不等写入write 变 4。read 在 5 时nums[5] 3nums[write - 2] nums[2]注意此刻 nums[2] 已经被覆盖成 23 和 2 不等写入write 变 5。返回 5。一切正确。这个写法唯一的心理门槛是你看到nums[write - 2]可能已经被覆盖过心里会不踏实。但仔细想想write 永远比 read 小write - 2这个位置一定已经被处理过它的值就是当前结果序列倒数第二个位置的值完全可靠。想通这一点这个写法就很香了。3.3 两个方案的取舍对比我把两种写法放在一张表里对比方便你按自己的习惯选。对比维度计数器版本向前看两位版本核心变量write countwrite 一个变量判断逻辑统计当前值出现次数count 2 才写和结果倒数第二个位置比较不等才写代码长度稍长约 15 行精简约 10 行可读性高适合新手理解中等需要先理解 write - 2 的含义扩展性改成“最多保留 k 个”需要改一个数改成“最多保留 k 个”也只需改一个数出错风险count 忘记重置是重灾区write - 2 比较语义想不通容易写错我个人的建议是第一次写用计数器版本因为它跟我们的直觉一致写错了也容易定位写熟之后把向前看两位的版本也吃透因为它在面试时更简洁而且能体现你对数组特性的理解深度。两个版本都掌握了这道题才算真正过关。4. 与第 26 题深度对比一通百通4.1 26 题的标准答案长什么样在讲 80 题和 26 题的关系之前先把 26 题的标准代码摆出来这样对比才有锚点。26 题要求每个元素只保留一个经典的快慢指针写法是这样的。int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) { return 0; } int write 1; for (int read 1; read numsSize; read) { if (nums[read] ! nums[write - 1]) { nums[write] nums[read]; write; } } return write; }注意这里的判断条件nums[read]和nums[write - 1]比较。write - 1 是结果数组的最后一个元素如果两者不等说明这是个新值写入后 write 前进。整个过程没有计数因为 26 题的规则就是“每个值只保留一个”只要发现当前值跟结果最后一个值不同就一定可以写入。这里有个重要的思维习惯你可以把 26 题的判断条件理解为“跟结果数组的最后一个位置比较”而不是“跟原数组上一个位置比较”。虽然很多实现里两个写法的效果相同但前者才能真正跟 80 题统一起来。4.2 从 26 到 80 的迁移只改了一个数字现在把两个题的关键对比放在一张表里。对比维度第 26 题第 80 题每个元素保留次数最多 1 次最多 2 次比较基准结果数组最后一个元素即 write - 1结果数组倒数第二个元素即 write - 2初始 write 值12需要处理空数组吗需要numsSize 0 时返回 0需要但可以统一写成 numsSize 2 返回 numsSize核心难点理解快慢指针的覆盖写理解“最多两个”如何体现在比较距离上从表里可以看得很清楚26 题就是“跟前面一个比较”80 题就是“跟前面两个比较”。如果把“最大保留数”记为 k那么 26 题的 k 是 180 题的 k 是 2。代码结构上只要把write - 1改成write - 2把初始 write 从 1 改成 2就完成了从 26 到 80 的迁移。所以我说这两道题本质上是一个题。你理解 26 题的快慢指针就应该能推出 80 题你理解了 80 题回头再看 26 题会觉得它只是 k 1 的特例。4.3 再进一步通用模板允许保留 K 个重复既然 k 1 和 k 2 都能用同一个结构解决那干脆直接写一个通用版本允许保留任意 k 个重复。这既是一个很好的思维延伸也是面试时展示能力的加分项。int removeDuplicatesK(int* nums, int numsSize, int k) { if (numsSize k) { return numsSize; } int write k; for (int read k; read numsSize; read) { if (nums[read] ! nums[write - k]) { nums[write] nums[read]; write; } } return write; }当 k 1 时这个函数就是 26 题的实现当 k 2 时它就是 80 题的实现。判断条件nums[read] ! nums[write - k]的语义是看当前值是否和结果序列中从后往前第 k 个元素相等。如果相等说明结果中至少已经有 k 个当前值再加就超了如果不相等说明当前值出现的次数还不足 k 次可以写入。这个模板非常值得背下来。因为 LeetCode 上有一类“删掉重复项”的变种题本质上都是调这个 k 值。你掌握了模板再遇到“最多保留三次”“最多保留四次”的变形就只需要改一个参数根本不需要重新想思路。面试官看到你能把一个具体题目抽象成通用解法通常会认为你对问题本质有理解而不是只会背题。5. 边界条件、测试用例与复杂度分析5.1 边界条件速查表写暴力解法时容易出错写双指针解法时同样要小心边界。我整理了五个最容易出问题的输入场景以及对应的预期输出。输入数组预期输出长度数组前 n 位结果说明[]0[]空数组直接返回 0[1]1[1]单个元素不用处理[1, 1, 1, 1]2[1, 1]全部相同只保留两个[1, 2, 3, 4]4[1, 2, 3, 4]本来就没有重复原样返回[1, 1, 2, 2, 3, 3]6原数组不变每个值恰好出现两次全部保留这张表可以用来快速验证你的代码是否正确。我刷题时的习惯是先跑题目给的示例再跑这几个边界用例全部通过才提交。边界用例几乎能覆盖百分之八十的隐藏错误。5.2 手动模拟一遍完整流程为了彻底看清双指针的运行过程我们用一个稍微复杂一点的例子来手动模拟[1, 1, 1, 2, 2, 3, 3, 3]预期输出长度是 6结果为[1, 1, 2, 2, 3, 3]。用计数器版本的逻辑read 下标nums[read]count是否写入write 变化112写入1 - 2213跳过2321写入2 - 3422写入3 - 4531写入4 - 5632写入5 - 6733跳过6最后 write 停在 6返回 6。注意一个细节write 变量的值刚好就是最终结果数组的长度因为它每写入一次就加一而写入次数就是保留的元素个数。再模拟一下向前看两位版本的同类数据。初始 write 2read 从 2 开始。read 在 2 时nums[2] 1nums[0] 1相等跳过read 在 3 时nums[3] 2nums[write - 2] nums[0] 1不等写入write 变 3read 在 4 时nums[4] 2nums[write - 2] nums[1] 1不等写入write 变 4read 在 5 时nums[5] 3nums[write - 2] nums[2]此时 nums[2] 已被覆盖为 23 和 2 不等写入write 变 5read 在 6 时nums[6] 3nums[write - 2] nums[3]nums[3] 是 23 和 2 不等写入write 变 6read 在 7 时nums[7] 3nums[write - 2] nums[4]此时 nums[4] 是 33 和 3 相等跳过。最终 write 也是 6。两个版本殊途同归。5.3 复杂度分析为什么 O(n) 已经是最优时间上数组从头到尾只扫了一遍每个元素最多被 read 看一次所以时间复杂度是 O(n)。空间上只用了 write、read、count 三四个整型变量没有申请额外数组所以空间复杂度是 O(1)。这两个指标对这道题来说已经是最优。有人可能会问数组有序能不能用二分查找或者更快的办法跳过一大段重复元素理论上可以但实际没意义因为你最终还是要一个个把元素搬到前面来除非重复段极长否则分段的收益很小反而增加代码复杂度。LeetCode 的判题数据也不会因为你用了花哨的跳跃而给出额外分稳妥的 O(n) 双指针就是标准答案。另外C 语言版本还有一个隐性问题numsSize的类型是 int当数组长度为 1 时numsSize 2会直接返回 1这个分支把长度 0、1、2 全部处理掉了避免了 write 初始值超出数组边界的风险。这种“先用边界条件截断”的写法在 C 语言里特别重要因为 C 不会帮你检查数组越界一旦 write 从 2 开始但数组长只有 1你后面必然访问越界结果不可预测。6. 实践中踩过的坑与排查方法6.1 高频错误自查表我刷这道题时踩过坑也看过不少人在评论区贴过自己的错误代码大约有五个错误出现频率最高几乎覆盖了所有提交失败的情况。错误类型错误代码示例后果没处理短数组直接int write 2就开循环数组长度小于 2 时越界访问判断条件用错写成nums[read] ! nums[read - 1]会保留三个相同值count 忘记重置只在相等时加一不等时没重置新值的计数延续旧值误判指针语义混淆把 write 当成已写入元素个数返回 write - 1返回值比实际长度小 1循环边界错误read 从 0 开始write 也从 0 开始第一个元素被跳过或重复写入先说第一个错误。如果你用向前看两位的写法一定要先判断numsSize 2直接返回。否则数组只有两个元素时write 2循环虽然没有进入但后面的代码如果还想访问 nums[write - 2]就会读到一个不存在的下标。很多人在 LeetCode 上报出奇怪的运行时错误回去一查就是这里漏了判断。第三个错误很隐蔽。计数器版本里你要保证“遇到不同值时重置 count 1”这个动作要和“读取新元素”同步。如果忘了重置连续三个 1 之后出现一个 2count 还停留在 3那么 2 会被误判为“已经出现过三次”直接被跳过结果丢失一个 2。这种错误不会让程序崩溃但会让结果悄无声息地少元素最危险。第四个错误主要出现在返回值上。write 的含义是“下一个可写入的位置”它同时就是结果数组的长度。很多人在循环结束后习惯性地返回 write - 1因为“最后一个元素的下标 1”才是长度。但 write 本身已经是从 0 开始计数后的长度你减一反而少了一个。举个最简单的例子原始数组是[1, 2]没有重复循环结束后 write 2返回 2 才是正确答案返回 1 就错了。6.2 现场排查的四个步骤我自己在调试这类双指针题目时有一套固定流程比瞎打 printf 高效得多分享给你。第一步先跑题目自带示例。LeetCode 每个题都有示例第一个示例通常是精心设计的包含各种小陷阱。比如 80 题的示例是[1, 1, 1, 2, 2, 3]它同时包含了“连续三个 1”和“恰好两个 2”足够暴露大部分问题。第二步跑一遍你自己构造的边界用例。我的固定组合是空数组、单个元素、两个相同元素、两个不同元素、全部相同的最长数组。这些用例代码量小你可以心算结果一旦不对劲马上能定位。第三步在循环里打印关键变量。具体来说每一轮输出 read、write、count 三个值再输出当前数组的整体状态。拿计数器版本来说你可以在每次循环结束时打印看看 write 增长的位置是否符合预期。for (int read 1; read numsSize; read) { // ... 原有逻辑 printf(read%d write%d count%d\n, read, write, count); for (int i 0; i numsSize; i) { printf(%d , nums[i]); } printf(\n); }看到实际输出后大多数错误会一目了然。比如 count 没有重置你会看到某个 read 明明是新值count 却还在高位比如 write 增长慢了你会看到数组有效部分缺失元素。第四步对比两个版本的代码。如果你有计数器版本和向前看两位版本用同一个测试用例分别跑一遍结果应该完全一致。如果一边正确一边错误那错误通常出在“比较基准”上回去检查是 write - 1 还是 write - 2 就会发现问题。这个方法让我省了很多排查时间也帮助我真正理解了两种写法的等价性。最后分享一个我后来的刷题习惯把 26 题、80 题和 27 题移除元素放在同一天刷。27 题是不看重复规则的直接移除特定值用的也是快慢指针26 题是每个值留一个80 题是每个值留两个。三题放在一起你会发现它们骨架完全一致只是判定条件换一下。这种成组刷题的方式比单独刷十道互不相关的题更能锻炼“识别题目模式”的能力。等你见多了看到“有序数组 原地去重 最多保留 k 个”这个组合基本不用想就能写出通用模板那才是真的把这一类型题吃透了。
