LeetCode 80题详解：C语言双指针原地删除有序数组重复项II

刷 LeetCode 的时候很多人 26 题过了就顺手点开 80 题觉得“无非是把最多出现一次改成两次”。我第一次做 80 题也是这么想的把 26 题的代码里slow - 1改成slow - 2然后提交结果被[1,1,1,2,2,2,3]这种用例教做人了。这篇文章就用 C 语言把 LeetCode 80删除有序数组中的重复项 II讲透从题目细节、双指针思路、完整代码到和 26 题的对比以及我实际踩过的坑一次说清楚。不管你是刚接触 C 语言的初学者还是在准备笔试面试、想巩固双指针套路的同学这篇都值得花十分钟看完。1. 题目在说什么先别急着写代码把三个细节抠清楚1.1 输入输出与函数签名题目给的是一个“非严格递增排列”的数组也就是升序数组相同元素必然相邻。要求原地删除重复出现的元素让每个元素最多出现两次然后返回删除后数组的新长度。不能开额外数组空间复杂度必须是 O(1)。举个例子输入nums [1,1,1,2,2,3] 输出5nums 变为 [1,1,2,2,3]LeetCode 上 C 语言的函数签名是这样int removeDuplicates(int* nums, int numsSize);nums是数组首地址numsSize是元素个数返回值是处理后的新长度。1.2 三个容易忽略的细节第一“原地删除”不是真的删除而是覆盖。数组的内存长度在函数调用时已经固定了你不可能真的把它变短你只需要保证数组前 k 个位置是最终结果返回 k。第二LeetCode 判题时只检查返回的 k 和nums[0]到nums[k-1]这些位置后面残留什么数据它根本不管。我见过有人担心“nums 后面还留着旧值会不会被判错”完全不会这是题目设计好的。第三C 语言里函数参数nums是int*指针不是数组名不要在函数内部用sizeof(nums)/sizeof(nums[0])去算长度。在 64 位系统上sizeof(nums)是 8不是数组总字节数这样算出来一定错。老老实实用numsSize。2. 解题思路的拐点从“和前一个比”到“和倒数第二个比”2.1 先回顾 26 题的双指针逻辑26 题要求“每个元素最多出现一次”。经典双指针写法是这样int removeDuplicates(int* nums, int numsSize) { if (numsSize 0) { return 0; } int slow 1; for (int fast 1; fast numsSize; fast) { if (nums[fast] ! nums[slow - 1]) { nums[slow] nums[fast]; slow; } } return slow; }这里slow是“下一个要写入的位置”同时它也是“当前已经处理好的区域长度”。fast负责往前扫描如果fast指向的值和已经处理区域里最后一个值不同说明这是一个需要保留的新值就把它写到slow位置然后slow。这个逻辑能成立是因为数组有序重复元素都挤在一起。slow - 1就是保留区最后那个数只要当前值和它不一样就一定是新的一段值的开头。2.2 80 题为什么可以直接把 1 换成 280 题允许每个元素最多出现两次那么前两个元素无论如何都应该保留不需要任何比较。所以slow的初始值从 1 变成 2比较对象也从nums[slow - 1]变成nums[slow - 2]。if (nums[fast] ! nums[slow - 2]) { nums[slow] nums[fast]; slow; }这里nums[slow - 2]是什么它是已处理保留区里倒数第二个位置。举个例子如果目前保留区是[1,1]slow 4那么nums[slow - 2]就是nums[2]也就是保留区倒数第二个元素。当fast指向的值和它相等说明这个值在保留区里已经出现两次了再放进去就是第三个必须跳过。一句话概括这个思路我不关心前面到底有几个重复值我只保证“保留区最后两个”和“当前扫描值”不同。如果一样说明再放就超了如果不一样说明当前值最多也就刚出现一次放心写进去。2.3 手动走查一组用例比背代码有用得多拿nums [0,0,1,1,1,1,2,3,3]走一遍期望结果长度是 7数组前 7 位是[0,0,1,1,2,3,3]。fastnums[fast]slownums[slow-2]比较结果动作初始-2---212nums[0]0不等写 nums[2]1, slow3313nums[1]0不等写 nums[3]1, slow4414nums[2]1相等跳过514nums[2]1相等跳过624nums[2]1不等写 nums[4]2, slow5735nums[3]1不等写 nums[5]3, slow6836nums[4]2不等写 nums[6]3, slow7注意 fast4 和 fast5 这两个位置它们的值都是 1此时保留区是[0,0,1,1]nums[slow-2]正好是保留区里倒数第二个 1所以判定“1 已经保留满两个了跳过”。fast7 时nums[slow-2]读的是nums[3]也就是保留区里的 1虽然此时nums[3]还是 1但数组里这个位置后面已经被改过整个处理过程都只看保留区边界不受原数组残留值的干扰。3. C 语言实现推荐写法、通用版本、反面写法3.1 推荐实现slow - 2 隔位比较先上完整代码int removeDuplicates(int* nums, int numsSize) { if (numsSize 2) { return numsSize; } int slow 2; for (int fast 2; fast numsSize; fast) { if (nums[fast] ! nums[slow - 2]) { nums[slow] nums[fast]; slow; } } return slow; }逐行拆一下if (numsSize 2)是必须的特判。数组长度不超过 2 时就算所有元素都相同也不可能出现“某个元素超过两次”的情况直接返回原长度。如果没有这个特判slow 2当numsSize 1或 0 时循环根本不会执行但返回值会是 2这就错了。slow 2语义是“前两个位置直接保留从第三个位置开始决定要不要写入”。循环里fast也从 2 开始因为前两个元素不需要检查。判断条件用nums[fast] ! nums[slow - 2]不等就写相等就跳过。最终返回slow它恰好就是去重后的数组长度。时间复杂度 O(n)空间复杂度 O(1)。整个算法只扫了一遍数组没有任何额外分配完全满足题目要求。3.2 泛化版本一个函数解决“最多保留 k 个”既然 26 题是“最多保留 1 个”80 题是“最多保留 2 个”那很自然想到如果题目改成“最多保留 k 个”代码是不是也长一样答案是肯定的int removeDuplicatesK(int* nums, int numsSize, int k) { if (numsSize k) { return numsSize; } int slow k; for (int fast k; fast numsSize; fast) { if (nums[fast] ! nums[slow - k]) { nums[slow] nums[fast]; slow; } } return slow; }26 题就是removeDuplicatesK(nums, numsSize, 1)80 题就是removeDuplicatesK(nums, numsSize, 2)。面试或者笔试遇到这类题直接套这个模板比临时推边界条件快得多。我后来写这类题基本不再单独记 26 和 80 的代码只记这个通用模板。3.3 计数器写法能跑但我不推荐网上也有用计数器实现的版本大致长这样int removeDuplicates(int* nums, int numsSize) { int j 0; int count 0; for (int i 0; i numsSize; i) { if (i 0 nums[i] nums[i - 1]) { count; } else { count 1; } if (count 2) { nums[j] nums[i]; j; } } return j; }这套逻辑在有序数组上确实能跑出正确答案。但我不推荐在面试或笔试时用原因有三个一是count的语义太重。你得时刻记住什么时候重置、什么时候累加、为什么count 2才写。一旦面试官追问“如果保留 k 个你怎么改”计数器版本要改的地方远多于双指针版本。二是它比较的是nums[i]和nums[i - 1]这个i - 1原数组位置可能在之前被覆盖过。在有序数组上结果碰巧是对的但你要向别人解释清楚“为什么覆盖不影响判断”解释成本很高。三是双指针版更接近问题本质。slow就是保留区边界nums[slow - k]就是“已经出现过的第 k 个位置”语义清清楚楚讲起来也方便。所以如果你还没有形成自己的写法我建议直接用双指针版。4. 与 26 题的对比看起来只差一个数字实际是两个维度4.1 题目差异对照表对比项LeetCode 26LeetCode 80最多保留数量1 个2 个比较对象nums[fast] ! nums[slow - 1]nums[fast] ! nums[slow - 2]slow 初始值12fast 初始值12空数组特判numsSize 0numsSize 2难度简单中等代码层面确实只差了几个数字但这背后是两个层次的思维26 题只需要“和前一个比”本质上是一维的只要不是重复出现的第一个值就保留。80 题需要“和倒数第二个比”本质上是在处理“一个值最多占两个坑位”的容量限制。你可以把slow - k理解成“保留区对当前值开放的最后一个允许位置”这个位置之前的 k 个位置已经被这个值占满当前值就不能再进来了。4.2 一个必翻车的改法用nums[fast] ! nums[fast - 1]很多教程里 26 题用的是另一种写法if (nums[fast] ! nums[fast - 1]) { nums[slow] nums[fast]; }26 题这样写是可以过的因为数组有序nums[fast - 1]是当前扫描位置前一个元素只要当前值和前一个不同就说明是新值开头。但千万不要把这个习惯带到 80 题我就在这上面翻过车。拿[1,1,1,2,2,2,3]试验错误写法是这样int slow 2; for (int fast 2; fast numsSize; fast) { if (nums[fast] ! nums[fast - 1]) { nums[slow] nums[fast]; } }走查一下fast2nums[2]1nums[1]1相等跳过fast3nums[3]2nums[2]1不等写nums[2]2slow3fast4nums[4]2nums[3]2相等跳过fast5nums[5]2nums[4]2相等跳过fast6nums[6]3nums[5]2不等写nums[3]3slow4。最后返回 4正确应该是 5。问题出在哪出在 fast4 时第二个 2 本来应该写入但因为nums[4]和nums[3]相等被错误跳过。nums[fast - 1]只能告诉你“原数组相邻两个值等不等”它不能告诉你“这个值在保留区里已经出现了几次”。一旦slow落后于fastnums[fast - 1]还可能已经被覆盖比较结果就更不可信。4.3 复杂度、判题细节与代码风格对比两个题的时间复杂度都是 O(n)空间复杂度都是 O(1)差别在边界处理。26 题的空数组特判必须写否则slow 1返回 1数组是空的也返回 1直接错。80 题的numsSize 2特判更宽因为长度不超过 2 的数组无论如何都满足“最多出现两次”的条件。代码风格上我建议 26 题也用通用模板写也就是slow k比较nums[slow - k]这样两道题的写法完全统一不容易记混。你要是非把 26 题和 80 题当成两个独立解法背到考场上很容易把slow初始值、比较下标哪个是 1 哪个是 2 搞反。5. 本地验证与调试C 语言做题的正确姿势5.1 写一个 main 函数把样例全部跑一遍LeetCode 上做题只需要提交函数但本地调试时我习惯自己写一个main把所有样例和边界用例一次性跑完。完整代码贴出来可以直接复制编译#include stdio.h int removeDuplicates(int* nums, int numsSize) { if (numsSize 2) { return numsSize; } int slow 2; for (int fast 2; fast numsSize; fast) { if (nums[fast] ! nums[slow - 2]) { nums[slow] nums[fast]; slow; } } return slow; } void test(int* nums, int numsSize) { int len removeDuplicates(nums, numsSize); printf(len %d: , len); for (int i 0; i len; i) { printf(%d , nums[i]); } printf(\n); } int main() { int a[] {1, 1, 1, 2, 2, 3}; test(a, sizeof(a) / sizeof(a[0])); int b[] {0, 0, 1, 1, 1, 1, 2, 3, 3}; test(b, sizeof(b) / sizeof(b[0])); int c[] {1, 1, 1, 1, 1}; test(c, sizeof(c) / sizeof(c[0])); int d[] {1, 2, 3, 4, 5}; test(d, sizeof(d) / sizeof(d[0])); int e[] {1, 1}; test(e, sizeof(e) / sizeof(e[0])); return 0; }在你的 VSCode 或者命令行里编译运行gcc -g -o test test.c ./test输出应该是len 5: 1 1 2 2 3 len 7: 0 0 1 1 2 3 3 len 2: 1 1 len 5: 1 2 3 4 5 len 2: 1 1这个测试函数把结果和原始数组一起打印方便你肉眼确认前 k 位是否正确。注意我用了sizeof(a) / sizeof(a[0])计算数组长度这个技巧只能用在 main 里真正定义数组的场景函数内部的指针参数不能用前面已经强调过了。5.2 边界用例空数组、长度 1、长度 2、全相同、全不同刷数组题最容易漏边界我整理了一份常用用例清单建议每个题都跑一遍用例输入期望输出空数组[]0单元素[1]1双元素相同[1,1]2双元素不同[1,2]2全相同[1,1,1,1,1]2全不同[1,2,3,4,5]5混合重复[1,1,1,2,2,2,3]5这些用例覆盖了numsSize 2特判、循环不执行、连续重复、交错重复等主要分支。每次写完代码先跑这份清单能省下大量提交被罚时的时间。5.3 gdb 观察 slow 和 fast一次“亲眼所见”的排查有一次我把循环条件写成了fast numsSize本地测试某些用例居然没崩提交到 LeetCode 就报运行时错误。后来用 gdb 才定位到问题。编译的时候加-g参数保留调试信息gcc -g -o test test.c gdb ./test在 gdb 里打断点、运行、单步观察break removeDuplicates run print slow print fast print nums[slow-2] continue-g编译后变量名都能直接看。那次我看到fast一路跑到了numsSize也就是数组最后一个元素的后面再去读nums[fast]就是越界访问。虽然当时数组后面恰好是合法内存没立刻崩但这种未定义行为迟早出事。如果你用的是 VSCode 的 C/C 插件可以直接在行号左边打断点然后在“运行和调试”面板里看变量变化效果比 gdb 命令行更直观。我在本地跑 LeetCode 题时常用的组合就是 VSCode GCC配合断点调试做数组、指针相关的题效率高不少。C 语言里数组越界不一定会马上报错因为越界访问的往往是相邻内存可能“碰巧”还能读出值来。这种问题用眼睛看代码很难发现最好的办法就是调试器里把fast、slow这些下标变量打出来看它们是否超出了合理范围。6. 这类题背后的通用思路与适用边界6.1 从 k1、k2 到 k任意值再回头看 3.2 的通用代码你会发现整套逻辑其实只需要两个信息slow保留区边界也是保留区当前长度比较nums[fast]和nums[slow - k]判断当前值如果在保留区里再放一个会不会让它的连续出现次数超过 k。这个模板可以直接应对面试官的各种变体比如“最多保留 3 个”“最多保留 n 个”。把 k 当作参数传进去就再也不用担心改代码时把某个数字漏掉。这也是我推荐把 26 题当成 k1 特例去记忆的原因题目会变套路不变。6.2 为什么“有序”是这个算法的命门这个算法的正确性建立在数组有序的前提上。因为有序相同的值必然相邻所以“保留区最后 k 个位置”才能代表“这个值在当前出现的所有情况”。如果数组无序比如[1,2,1,2,1]用slow 2的算法跑fast2nums[2]1nums[0]1相等直接跳过后面的 1 也都会被跳过。但原数组里 1 只出现在位置 0、2、4如果题目要求“每个元素最多出现两次”位置 2 的 1 本来应该保留结果被错误丢弃。所以说只要题目里少了“有序”两个字这个算法就不成立。遇到无序数组要处理同类问题你只能先排序或者用哈希表统计频率然后重新组织数组那就不再是这道题的考点了。6.3 双指针覆盖思想还能用在哪“一个指针维护已处理区域一个指针向前探索”这个模式在 LeetCode 里远不止 26 和 80 两题。27 题“移除元素”是slow维护不含目标值的区域fast遍历整个数组283 题“移动零”本质上是把非零元素先挪到前面再在后面补零链表里的慢快指针找中间节点、检测环也是同一个思路的变体。把这些题放在一起看你会发现双指针的核心就一句话用两个下标或指针把一趟扫描分成“已处理区”和“待处理区”每次迭代只决定一个元素的去留把数组原地改写。时间 O(n)、空间 O(1) 的原因也在这里——每个元素最多被扫描一次、最多被写入一次。最后分享一个我自己的习惯刷这类“原地去重”的题拿到题目先不要写代码先问自己三个问题——返回值是什么前几个位置必须正确哪些位置可以无脑保留这三个问题想清楚slow的初始值、比较下标的k、特判条件就全出来了。把这套流程走熟了以后遇到 26、80甚至面试官现场改的变体题你都能在几分钟内写出不越界、不翻车的解法。