做了这么多年算法题LeetCode 26这道“删除有序数组中的重复项”是我觉得最值得反复琢磨的简单题之一。它表面上就是让你去掉数组里重复的数但真动起手来涉及到的原地修改、双指针、边界处理……每一处都是面试官最爱挖坑的地方。无论你是刚开始刷题的萌新还是准备跳槽想快速过一遍热题的老手把这道题吃透性价比特别高。很多人在第一次写这道题时会本能地想到“那我碰到重复的就删掉一个”结果发现数组是连续内存结构删除一个元素后面所有元素都要往前挪效率低不说索引还特别容易搞乱。LeetCode 26真正想考察的是你会不会用一个更优雅的方式来“原地”解决问题。这篇文章就带你从题目读懂、思路推导、代码实现到面试延伸把这道经典题彻底嚼碎。1. 题目到底在考什么先看懂“有序数组”和“原地”两个限定1.1 先用大白话翻译一遍题目题目原文很简洁给你一个按非递减顺序排列的数组 nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。我习惯把这类题先翻译成大白话数组已经从小到大排好了重复的数字肯定是连在一起的我需要让每个数字只留一个多余的全部清掉而且不能新建数组只能在原数组上动手最后告诉别人“新数组有多长”。举一个最简单的例子nums [0,0,1,1,1,2,2,3,3,4]处理完之后要返回 5同时数组的前 5 位要变成 [0,1,2,3,4]。注意题目对数组第 5 位之后的内容没有要求是 0、是 5、还是原本的残留值都不影响判题这一点在实际编码时非常重要。这道题属于 LeetCode 热门 100 题里的常客也被归入简单题一档。但它作为“快慢指针原地去重”的启蒙题后续的 27 移除元素、80 删除有序数组中的重复项 II、283 移动零全是它的变体。把这道题的逻辑吃透等于同时拿下了好几道题。1.2 “有序”这个限定为什么是突破口数组有序这是整道题能简化的核心前提。因为有序所有重复元素必然相邻比如出现 1、1、1它们一定是紧挨着的不会出现 1、2、1 这种重复相隔的情况。所以我们只需要比较相邻的两个元素就能判断是否有重复。如果数组是无序的去重就得另想办法。比如用一个哈希表记录出现过的数字每遍历到一个新元素就查一下表出现过就跳过没出现过就保留。这样当然也能去重但时间复杂度虽然是 O(n)额外空间复杂度却变成 O(n)而且数字之间的相对顺序一旦要求保持处理起来会更麻烦。你可能会问那无序数组用“先排序再去重”行不行可以但排序本身就有 O(n log n) 的时间成本。LeetCode 26 直接给你一个排好序的数组等于是把最重的那部分工作提前做完了剩下要考的就是你能不能利用“相邻即重复”这个规律写出一个只扫一遍的算法。1.3 “原地”限制背后的工程考量“原地”二字往往被新手忽略但它是这道题真正的考点。原地操作意味着不能用额外数组空间复杂度必须控制在 O(1)。为什么 LeetCode 要强调这一点因为真实工程里数组可能非常非常大比如几十万条日志、几百万个 ID如果每个操作都复制一份新数组内存瞬间就爆了。C 里的 vector 有个 erase 方法很多第一次刷这道题的人会直接写循环加 erase。思路是没错但 erase 操作的时间复杂度是 O(n)因为删除中间元素后后面所有元素都要整体搬移。假如一个数组有一万个重复元素每删一次就搬一次最坏情况会退化到 O(n^2)。LeetCode 的判题系统给出的测试用例里就专门准备了大数组来卡这种写法提交后直接超时。所以“原地”这个要求本质上是逼你思考我不物理删除而是“覆盖”行不行我不动后面多余的元素只用前面的位置来构建最终结果行不行这就是双指针解法的出发点。2. 双指针解法拆解一个向前探路一个驻守写入2.1 为什么说双指针是“最优解”解决这类数组原地问题双指针是教科书级别的答案。时间复杂度 O(n)空间复杂度 O(1)只扫描一遍数组不申请额外空间从复杂度上已经到头了。双指针按移动方向分为很多种同向快慢指针、左右对撞指针、滑动窗口指针等。本题用的是同向快慢指针也叫快慢指针。它的核心思想是让两个指针同时从左往右走其中一个指针走得快负责“探路”另一个指针走得慢负责“写入”。快指针在前面发现了一个新元素就把这个元素“告诉”慢指针慢指针在它所在的位置把这个值记下来然后前进一位。你可以把它想象成两个人一起整理一排货架慢的人站在货架前负责摆放。快的人从第一个货位开始往后走看到商品编号变了就喊一声“这个编号没出现过可以上架”。慢的人听到后就把这个商品放到自己面前的位置然后往前走一步等待下一次指令。整个过程货架没有被搬空重排只是在局部做了覆盖。2.2 指针语义与移动规则详解双指针的实现有好几种写法我推荐一种最不容易出错、也最适合用来向面试官讲解的方式。先定义两个变量慢指针 slow指向下一个可以写入新元素的位置同时它前面所有元素已经是去重后的结果。快指针 fast遍历整个数组找到每个“第一次出现”的元素。遍历时我们从索引 1 开始让 fast 走。为什么不是 0因为第一个元素无论重复与否都该被保留nums[0] 一定是最终结果的第一个元素。慢指针从 1 开始因为它前面已经有了 nums[0] 这个“保底元素”下一个要写入的位置是索引 1。快指针每到一个位置我们比较 nums[fast] 是否等于 nums[slow - 1]。这里 nums[slow - 1] 的含义是什么它是慢指针已经写入的最后一个元素也就是当前去重后数组的最后一个值。如果 nums[fast] 和它不一样说明这个元素是第一次出现值得保留于是我们把它写到 nums[slow]然后 slow。比较 nums[fast] 和 nums[slow-1]而不是和 nums[fast-1]这个细节很多人没想明白。用 nums[fast-1] 也可以判断相邻是否重复因为数组有序但用 nums[slow-1] 有一个额外好处即使脑子里残留着“物理删除每个重复项”的思路这种写法也能保证慢指针之前的区间是严格不重复的语义更清晰。两种写法都能通过我习惯用 slow-1因为它和返回 slow 这个逻辑浑然一体。2.3 两个容易翻车的边界细节第一个边界是空数组。如果 nums.length 为 0直接返回 0。不处理这一步后面访问 nums[0] 就会越界。很多第一次写的人会忘导致提交后在空数组用例上报错。第二个边界是数组长度为 1。这种时候根本不需要做任何操作因为一个元素必然没有重复直接返回 1 即可。其实你按统一逻辑写slow 初始为 1fast 从 1 开始循环体根本进不去最后返回 slow 就是 1不会错。真正需要注意的是返回的是 slow 而不是 slow 1。slow 记录的是“已经写入元素的下一个位置”又因为写入是从索引 0 开始的所以 slow 本身就等于结果数组的长度。比如原数组 [1,1,2]最终 [1,2] 占两个位置slow 恰好为 2返回 2 就是正确答案。这里最容易写错成 slow1一加就多了一个。还有一类情况是数组中所有元素都不重复比如 [1,2,3,4,5]。这种情况下 fast 每走一步nums[fast] 都不等于 nums[slow-1]于是每步都会写入和移动 slow最终 slow 等于 n返回 n等价于什么都没删完全正确。3. 三种语言的完整实现与逐行注释3.1 C 实现与防坑要点C 是刷 LeetCode 最主流的语言之一写这道题时可以完全避开 vector 的 erase 操作直接用索引下标来维护双指针。这段实现里最值得注意的坑有两个第一个千万不要在循环里对 nums 做 erase 操作否则会因为元素搬移导致下标错乱我能贴出的代码里连看都看不到 erase这就对了。第二个注意 i 从 1 开始遍历不是从 0否则会把 nums[0] 和 nums[0] 比较一次虽然结果没错但白白多走一轮。复杂度方面遍历了一轮数组所以是 O(n)只用了两个 int 型变量空间是 O(1)。3.2 Python 实现与“原地修改”的坑Python 的写法最贴近伪代码逻辑非常清晰。但 Python 有一个其他语言不太一样的点列表是可变对象函数里直接对 nums 做 nums[write] ... 操作会影响到外部变量这点恰好符合题目要求的“原地修改”。比较常见的错误写法是for 循环里拿到重复元素后用 nums.remove(value) 或 del nums[i] 去删。这样的确能在 Python 中实现“物理删除”但 remove 本身是 O(n) 操作因为要找到目标元素并搬移后续元素del 也会触发列表的重新整理。在 LeetCode 的大数据量测试用例下这种写法很容易超时。更隐蔽的问题是边遍历边删除会导致元素索引变化for 循环的 i 还可能越界或跳过一个元素调试起来非常痛苦。还有部分人会用 nums[:] new_list。这种方式确实实现了原地替换因为切片赋值是在原列表对象上做整体修改外部引用依然指向同一个对象。但它需要一个新列表额外空间是 O(n)不符合题目的“原地”初衷。面试时这样写面试官大概率会追问一句“你额外用了多少空间”。3.3 Java 实现与复杂度论证Java 的 int[] 数组长度固定没法真正“变短”但题目只要求你返回新长度数组后面的多余位置是否保留不重要所以写法同样很直接。Java 和 C 的这段代码逻辑完全一致唯一的细微差别是 Java 的数组没有 length() 方法只有 length 属性。另外Java 里如果面试官要求你“真正缩减数组”你可以用 Arrays.copyOf 截断但在本题目下直接返回 slow 即可。后面如果写 LeetCode 80每个元素最多保留两次只需要把比较逻辑从 nums[fast] ! nums[write - 1] 改成 nums[fast] ! nums[write - 2]其他完全不用动。4. 高频问题、面试追问与同型题目4.1 一张表查完常见报错与边界值我整理了一个速查表覆盖我在实际刷题和辅导别人时遇到过的高频问题对照着排查会快很多。问题现象常见原因解决办法空数组越界没判断 nums.length 0 就访问 nums[0]第一步先处理空数组直接返回 0返回长度比预期大 1误写成 slow 1 或 write 1理清语义write 指向下一个写入位置等于当前长度返回长度比预期小 1误把 write 初始化为 0write 初始化为 1因为首个元素必保留数组前几位结果不对覆盖写入时没有用慢指针位置确保写入位置是 nums[write] 或 nums[slow]不是 nums[fast]使用 erase/remove 导致超时每次删除都是 O(n) 搬移最坏退化为 O(n^2)改用覆盖写入不物理删除边遍历边删除索引越界删除元素后 i 应回退但漏了回退放弃删除思路用双指针原地覆盖这些坑里最不值得踩的就是“边遍历边删除”。记住一个核心认知数组的删除成本非常高除非数据量极小否则能用覆盖就不用删除。4.2 面试官最常追问的四个变体面试官基本不会只满足于让你把这道题写出来他一定会追问变体考察你是不是真的理解了题目本质。第一个变体是如果数组是无序的怎么办这时“比较相邻元素”的前提就失效了你可以先排序再套双指针时间复杂度 O(n log n)或者用一个哈希集合记录出现过的元素遍历一遍即可时间复杂度 O(n)额外空间 O(n)。面试官会希望你说出时间和空间的 trade-off。第二个变体是每个元素最多可以保留两次怎么做这就是 LeetCode 80。核心改动只在一个地方把快慢指针的比较对象从 nums[write-1] 改为 nums[write-2]。因为 write-2 是“已保留结果的倒数第二个位置”如果当前元素和它相等说明当前元素已经出现了至少两次需要跳过如果不相等说明当前元素最多只出现了一次或两次可以保留。这个改动非常小但体现出你对双指针的理解深度。第三个变体是不只是返回长度还要返回去重后的数组。这个问题在 Python 里可以用 nums[:] 截断在 C 里可以用 vector 的 resize或者干脆直接使用结果数组的前 slow 个元素。只要你自己心里清楚多余位置的元素不影响最终结果这个问题就不难。第四个变体是如果数组是 Java 的 ArrayList 或 C 的 list会有差别吗ArrayList 底层是数组本质上和 int[] 差不多用 get 和 set 双指针即可list 是链表结构删除操作是 O(1)但随机访问不如数组方便双指针策略要调整成迭代器写法。4.3 跳出题目原地覆盖思想在工程里的应用这道题里的覆盖写入思想在真实工程里处处可见。最常见的场景是日志清洗系统每天产生海量的有序日志需要去除重复的告警记录但又不能频繁申请新内存于是可以维护一个写入游标遍历原始日志流时只把“首次出现的告警类型”写入保留区。这种模式在数据处理管道、数据库压缩、文件去重工具里都有体现。再比如做视频帧抽稀要求每秒钟最多保留一帧关键帧视频帧序列本身按时间戳排序处理逻辑跟 LeetCode 80 几乎一模一样只是判断条件从“最多出现两次”变成“间隔至少超过多少毫秒”。当年我刚开始接触流式处理时看到这类需求总觉得要开一个临时文件或者新数组后来意识到这种“覆盖写入 游标”的思想能省一大笔内存才真正体会到算法题不只是刷题而是工程经验的提前预演。5. 刷完这道题后我总结的三个习惯5.1 先处理空集和单元素边界我见过太多人写算法题主逻辑写得飞快一到边界就翻车。处理数组题第一步永远是问自己数组为空怎么办长度为 1 怎么办这两个问题不想清楚后面代码写起来很容易越界或直接返回错误结果。我个人的习惯是不管题目多简单先写一个 if 判断长度的分支或者确保算法天然兼容长度 1 的情况。LeetCode 26 这道题只要把 write 初始化为 1从索引 1 开始遍历就能天然兼容空集空集直接返回 0和单元素数组循环不进返回 1。但“天然兼容”不等于“不用思考”你在写之前最好明确说出来空数组返回 0单元素返回 1这样代码 review 时也更有说服力。5.2 手写一段测试用例别直接提交写完代码不要着急点提交先在草稿纸上或者本地跑一遍小例子。比如 [1,1,2]、[0,0,1,1,1,2,2,3,3,4] 这种标准用例再想想 [1] 和 [] 这种边界。我在实际练习时会故意构造一个全是重复元素的数组比如 [7,7,7,7,7]手动模拟双指针移动过程看看 write 最终停在哪里。这种手写模拟的过程虽然慢但对训练思维非常有效。你跑多了之后会形成一种直觉看到原地数组题目第一时间想到快慢指针想到 write 指向下一个可写位置想到 nums[write - 1] 或 nums[write - 2] 的比较逻辑。5.3 记录复杂度推导过程刷题时我会在代码注释里写上时间复杂度和空间复杂度推导过程不是为了应付考试而是为了日后复习。LeetCode 26 的复杂度分析很简单但你要有能力正式地讲出来快指针遍历整个数组总操作次数是 n所以时间复杂度 O(n)额外只用了两个整数变量不随输入规模变化所以空间复杂度 O(1)。一旦你能把这种复杂度论证变成刷题的本能反应遇到任何新题就都不会怵。最后再说一个小技巧每次刷完一道题顺手看一下讨论区里别人有没有写出更简洁的版本。LeetCode 26 的题解区里有些答案是单指针加哨兵值有些是用元组解包做交换这些不同写法能帮你拓展思维边界。但核心永远是先理解原理再追求简洁这样才能真正把知识内化成自己的能力。
LeetCode 26：双指针原地去重，吃透经典数组算法题
做了这么多年算法题LeetCode 26这道“删除有序数组中的重复项”是我觉得最值得反复琢磨的简单题之一。它表面上就是让你去掉数组里重复的数但真动起手来涉及到的原地修改、双指针、边界处理……每一处都是面试官最爱挖坑的地方。无论你是刚开始刷题的萌新还是准备跳槽想快速过一遍热题的老手把这道题吃透性价比特别高。很多人在第一次写这道题时会本能地想到“那我碰到重复的就删掉一个”结果发现数组是连续内存结构删除一个元素后面所有元素都要往前挪效率低不说索引还特别容易搞乱。LeetCode 26真正想考察的是你会不会用一个更优雅的方式来“原地”解决问题。这篇文章就带你从题目读懂、思路推导、代码实现到面试延伸把这道经典题彻底嚼碎。1. 题目到底在考什么先看懂“有序数组”和“原地”两个限定1.1 先用大白话翻译一遍题目题目原文很简洁给你一个按非递减顺序排列的数组 nums请你原地删除重复出现的元素使每个元素只出现一次返回删除后数组的新长度。元素的相对顺序应该保持一致。我习惯把这类题先翻译成大白话数组已经从小到大排好了重复的数字肯定是连在一起的我需要让每个数字只留一个多余的全部清掉而且不能新建数组只能在原数组上动手最后告诉别人“新数组有多长”。举一个最简单的例子nums [0,0,1,1,1,2,2,3,3,4]处理完之后要返回 5同时数组的前 5 位要变成 [0,1,2,3,4]。注意题目对数组第 5 位之后的内容没有要求是 0、是 5、还是原本的残留值都不影响判题这一点在实际编码时非常重要。这道题属于 LeetCode 热门 100 题里的常客也被归入简单题一档。但它作为“快慢指针原地去重”的启蒙题后续的 27 移除元素、80 删除有序数组中的重复项 II、283 移动零全是它的变体。把这道题的逻辑吃透等于同时拿下了好几道题。1.2 “有序”这个限定为什么是突破口数组有序这是整道题能简化的核心前提。因为有序所有重复元素必然相邻比如出现 1、1、1它们一定是紧挨着的不会出现 1、2、1 这种重复相隔的情况。所以我们只需要比较相邻的两个元素就能判断是否有重复。如果数组是无序的去重就得另想办法。比如用一个哈希表记录出现过的数字每遍历到一个新元素就查一下表出现过就跳过没出现过就保留。这样当然也能去重但时间复杂度虽然是 O(n)额外空间复杂度却变成 O(n)而且数字之间的相对顺序一旦要求保持处理起来会更麻烦。你可能会问那无序数组用“先排序再去重”行不行可以但排序本身就有 O(n log n) 的时间成本。LeetCode 26 直接给你一个排好序的数组等于是把最重的那部分工作提前做完了剩下要考的就是你能不能利用“相邻即重复”这个规律写出一个只扫一遍的算法。1.3 “原地”限制背后的工程考量“原地”二字往往被新手忽略但它是这道题真正的考点。原地操作意味着不能用额外数组空间复杂度必须控制在 O(1)。为什么 LeetCode 要强调这一点因为真实工程里数组可能非常非常大比如几十万条日志、几百万个 ID如果每个操作都复制一份新数组内存瞬间就爆了。C 里的 vector 有个 erase 方法很多第一次刷这道题的人会直接写循环加 erase。思路是没错但 erase 操作的时间复杂度是 O(n)因为删除中间元素后后面所有元素都要整体搬移。假如一个数组有一万个重复元素每删一次就搬一次最坏情况会退化到 O(n^2)。LeetCode 的判题系统给出的测试用例里就专门准备了大数组来卡这种写法提交后直接超时。所以“原地”这个要求本质上是逼你思考我不物理删除而是“覆盖”行不行我不动后面多余的元素只用前面的位置来构建最终结果行不行这就是双指针解法的出发点。2. 双指针解法拆解一个向前探路一个驻守写入2.1 为什么说双指针是“最优解”解决这类数组原地问题双指针是教科书级别的答案。时间复杂度 O(n)空间复杂度 O(1)只扫描一遍数组不申请额外空间从复杂度上已经到头了。双指针按移动方向分为很多种同向快慢指针、左右对撞指针、滑动窗口指针等。本题用的是同向快慢指针也叫快慢指针。它的核心思想是让两个指针同时从左往右走其中一个指针走得快负责“探路”另一个指针走得慢负责“写入”。快指针在前面发现了一个新元素就把这个元素“告诉”慢指针慢指针在它所在的位置把这个值记下来然后前进一位。你可以把它想象成两个人一起整理一排货架慢的人站在货架前负责摆放。快的人从第一个货位开始往后走看到商品编号变了就喊一声“这个编号没出现过可以上架”。慢的人听到后就把这个商品放到自己面前的位置然后往前走一步等待下一次指令。整个过程货架没有被搬空重排只是在局部做了覆盖。2.2 指针语义与移动规则详解双指针的实现有好几种写法我推荐一种最不容易出错、也最适合用来向面试官讲解的方式。先定义两个变量慢指针 slow指向下一个可以写入新元素的位置同时它前面所有元素已经是去重后的结果。快指针 fast遍历整个数组找到每个“第一次出现”的元素。遍历时我们从索引 1 开始让 fast 走。为什么不是 0因为第一个元素无论重复与否都该被保留nums[0] 一定是最终结果的第一个元素。慢指针从 1 开始因为它前面已经有了 nums[0] 这个“保底元素”下一个要写入的位置是索引 1。快指针每到一个位置我们比较 nums[fast] 是否等于 nums[slow - 1]。这里 nums[slow - 1] 的含义是什么它是慢指针已经写入的最后一个元素也就是当前去重后数组的最后一个值。如果 nums[fast] 和它不一样说明这个元素是第一次出现值得保留于是我们把它写到 nums[slow]然后 slow。比较 nums[fast] 和 nums[slow-1]而不是和 nums[fast-1]这个细节很多人没想明白。用 nums[fast-1] 也可以判断相邻是否重复因为数组有序但用 nums[slow-1] 有一个额外好处即使脑子里残留着“物理删除每个重复项”的思路这种写法也能保证慢指针之前的区间是严格不重复的语义更清晰。两种写法都能通过我习惯用 slow-1因为它和返回 slow 这个逻辑浑然一体。2.3 两个容易翻车的边界细节第一个边界是空数组。如果 nums.length 为 0直接返回 0。不处理这一步后面访问 nums[0] 就会越界。很多第一次写的人会忘导致提交后在空数组用例上报错。第二个边界是数组长度为 1。这种时候根本不需要做任何操作因为一个元素必然没有重复直接返回 1 即可。其实你按统一逻辑写slow 初始为 1fast 从 1 开始循环体根本进不去最后返回 slow 就是 1不会错。真正需要注意的是返回的是 slow 而不是 slow 1。slow 记录的是“已经写入元素的下一个位置”又因为写入是从索引 0 开始的所以 slow 本身就等于结果数组的长度。比如原数组 [1,1,2]最终 [1,2] 占两个位置slow 恰好为 2返回 2 就是正确答案。这里最容易写错成 slow1一加就多了一个。还有一类情况是数组中所有元素都不重复比如 [1,2,3,4,5]。这种情况下 fast 每走一步nums[fast] 都不等于 nums[slow-1]于是每步都会写入和移动 slow最终 slow 等于 n返回 n等价于什么都没删完全正确。3. 三种语言的完整实现与逐行注释3.1 C 实现与防坑要点C 是刷 LeetCode 最主流的语言之一写这道题时可以完全避开 vector 的 erase 操作直接用索引下标来维护双指针。这段实现里最值得注意的坑有两个第一个千万不要在循环里对 nums 做 erase 操作否则会因为元素搬移导致下标错乱我能贴出的代码里连看都看不到 erase这就对了。第二个注意 i 从 1 开始遍历不是从 0否则会把 nums[0] 和 nums[0] 比较一次虽然结果没错但白白多走一轮。复杂度方面遍历了一轮数组所以是 O(n)只用了两个 int 型变量空间是 O(1)。3.2 Python 实现与“原地修改”的坑Python 的写法最贴近伪代码逻辑非常清晰。但 Python 有一个其他语言不太一样的点列表是可变对象函数里直接对 nums 做 nums[write] ... 操作会影响到外部变量这点恰好符合题目要求的“原地修改”。比较常见的错误写法是for 循环里拿到重复元素后用 nums.remove(value) 或 del nums[i] 去删。这样的确能在 Python 中实现“物理删除”但 remove 本身是 O(n) 操作因为要找到目标元素并搬移后续元素del 也会触发列表的重新整理。在 LeetCode 的大数据量测试用例下这种写法很容易超时。更隐蔽的问题是边遍历边删除会导致元素索引变化for 循环的 i 还可能越界或跳过一个元素调试起来非常痛苦。还有部分人会用 nums[:] new_list。这种方式确实实现了原地替换因为切片赋值是在原列表对象上做整体修改外部引用依然指向同一个对象。但它需要一个新列表额外空间是 O(n)不符合题目的“原地”初衷。面试时这样写面试官大概率会追问一句“你额外用了多少空间”。3.3 Java 实现与复杂度论证Java 的 int[] 数组长度固定没法真正“变短”但题目只要求你返回新长度数组后面的多余位置是否保留不重要所以写法同样很直接。Java 和 C 的这段代码逻辑完全一致唯一的细微差别是 Java 的数组没有 length() 方法只有 length 属性。另外Java 里如果面试官要求你“真正缩减数组”你可以用 Arrays.copyOf 截断但在本题目下直接返回 slow 即可。后面如果写 LeetCode 80每个元素最多保留两次只需要把比较逻辑从 nums[fast] ! nums[write - 1] 改成 nums[fast] ! nums[write - 2]其他完全不用动。4. 高频问题、面试追问与同型题目4.1 一张表查完常见报错与边界值我整理了一个速查表覆盖我在实际刷题和辅导别人时遇到过的高频问题对照着排查会快很多。问题现象常见原因解决办法空数组越界没判断 nums.length 0 就访问 nums[0]第一步先处理空数组直接返回 0返回长度比预期大 1误写成 slow 1 或 write 1理清语义write 指向下一个写入位置等于当前长度返回长度比预期小 1误把 write 初始化为 0write 初始化为 1因为首个元素必保留数组前几位结果不对覆盖写入时没有用慢指针位置确保写入位置是 nums[write] 或 nums[slow]不是 nums[fast]使用 erase/remove 导致超时每次删除都是 O(n) 搬移最坏退化为 O(n^2)改用覆盖写入不物理删除边遍历边删除索引越界删除元素后 i 应回退但漏了回退放弃删除思路用双指针原地覆盖这些坑里最不值得踩的就是“边遍历边删除”。记住一个核心认知数组的删除成本非常高除非数据量极小否则能用覆盖就不用删除。4.2 面试官最常追问的四个变体面试官基本不会只满足于让你把这道题写出来他一定会追问变体考察你是不是真的理解了题目本质。第一个变体是如果数组是无序的怎么办这时“比较相邻元素”的前提就失效了你可以先排序再套双指针时间复杂度 O(n log n)或者用一个哈希集合记录出现过的元素遍历一遍即可时间复杂度 O(n)额外空间 O(n)。面试官会希望你说出时间和空间的 trade-off。第二个变体是每个元素最多可以保留两次怎么做这就是 LeetCode 80。核心改动只在一个地方把快慢指针的比较对象从 nums[write-1] 改为 nums[write-2]。因为 write-2 是“已保留结果的倒数第二个位置”如果当前元素和它相等说明当前元素已经出现了至少两次需要跳过如果不相等说明当前元素最多只出现了一次或两次可以保留。这个改动非常小但体现出你对双指针的理解深度。第三个变体是不只是返回长度还要返回去重后的数组。这个问题在 Python 里可以用 nums[:] 截断在 C 里可以用 vector 的 resize或者干脆直接使用结果数组的前 slow 个元素。只要你自己心里清楚多余位置的元素不影响最终结果这个问题就不难。第四个变体是如果数组是 Java 的 ArrayList 或 C 的 list会有差别吗ArrayList 底层是数组本质上和 int[] 差不多用 get 和 set 双指针即可list 是链表结构删除操作是 O(1)但随机访问不如数组方便双指针策略要调整成迭代器写法。4.3 跳出题目原地覆盖思想在工程里的应用这道题里的覆盖写入思想在真实工程里处处可见。最常见的场景是日志清洗系统每天产生海量的有序日志需要去除重复的告警记录但又不能频繁申请新内存于是可以维护一个写入游标遍历原始日志流时只把“首次出现的告警类型”写入保留区。这种模式在数据处理管道、数据库压缩、文件去重工具里都有体现。再比如做视频帧抽稀要求每秒钟最多保留一帧关键帧视频帧序列本身按时间戳排序处理逻辑跟 LeetCode 80 几乎一模一样只是判断条件从“最多出现两次”变成“间隔至少超过多少毫秒”。当年我刚开始接触流式处理时看到这类需求总觉得要开一个临时文件或者新数组后来意识到这种“覆盖写入 游标”的思想能省一大笔内存才真正体会到算法题不只是刷题而是工程经验的提前预演。5. 刷完这道题后我总结的三个习惯5.1 先处理空集和单元素边界我见过太多人写算法题主逻辑写得飞快一到边界就翻车。处理数组题第一步永远是问自己数组为空怎么办长度为 1 怎么办这两个问题不想清楚后面代码写起来很容易越界或直接返回错误结果。我个人的习惯是不管题目多简单先写一个 if 判断长度的分支或者确保算法天然兼容长度 1 的情况。LeetCode 26 这道题只要把 write 初始化为 1从索引 1 开始遍历就能天然兼容空集空集直接返回 0和单元素数组循环不进返回 1。但“天然兼容”不等于“不用思考”你在写之前最好明确说出来空数组返回 0单元素返回 1这样代码 review 时也更有说服力。5.2 手写一段测试用例别直接提交写完代码不要着急点提交先在草稿纸上或者本地跑一遍小例子。比如 [1,1,2]、[0,0,1,1,1,2,2,3,3,4] 这种标准用例再想想 [1] 和 [] 这种边界。我在实际练习时会故意构造一个全是重复元素的数组比如 [7,7,7,7,7]手动模拟双指针移动过程看看 write 最终停在哪里。这种手写模拟的过程虽然慢但对训练思维非常有效。你跑多了之后会形成一种直觉看到原地数组题目第一时间想到快慢指针想到 write 指向下一个可写位置想到 nums[write - 1] 或 nums[write - 2] 的比较逻辑。5.3 记录复杂度推导过程刷题时我会在代码注释里写上时间复杂度和空间复杂度推导过程不是为了应付考试而是为了日后复习。LeetCode 26 的复杂度分析很简单但你要有能力正式地讲出来快指针遍历整个数组总操作次数是 n所以时间复杂度 O(n)额外只用了两个整数变量不随输入规模变化所以空间复杂度 O(1)。一旦你能把这种复杂度论证变成刷题的本能反应遇到任何新题就都不会怵。最后再说一个小技巧每次刷完一道题顺手看一下讨论区里别人有没有写出更简洁的版本。LeetCode 26 的题解区里有些答案是单指针加哨兵值有些是用元组解包做交换这些不同写法能帮你拓展思维边界。但核心永远是先理解原理再追求简洁这样才能真正把知识内化成自己的能力。
