InterviewGuide 刷题笔记：LeetCode 80 题《删除排序数组中的重复项 II》——双指针原地去重，允许每个元素最多出现两次

教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载导读LeetCode 80 题「删除排序数组中的重复项 II」是面试高频的原地数组去重问题给定一个已排序数组要求删除重复元素、使每个元素最多出现两次并返回新数组长度全程只能使用 O(1) 额外空间。它是 26 题每个元素最多一次的进阶版也是 InterviewGuide「精选力扣 300 题目之双指针」分类下的代表性中等题。读完本文你将掌握快慢指针覆盖法的核心思想、nums[len-2]这一关键判断的底层原理并能把解法推广到每个元素最多保留 k 个的通式从容应对同类变体。一、题目定位它在 InterviewGuide 双指针体系中的位置本题收录于 双指针题目分类目录与 75. 颜色分类、56. 合并区间、424. 替换后的最长重复字符 等题同属一个刷题系列原文档还单独收录了一份题目汇总版见 双指针 medium 合集。作者在文档标题中特别标注很好的题目原因在于它表面上是一道数组操作题实际考察的是**快慢指针双指针之一**的经典应用——一个指针负责遍历原数组另一个指针负责维护去重后有效区间的写入位置两者配合即可做到一趟扫描、原地完成。在动手之前先明确两个贯穿全题的算法概念InterviewGuide 在 算法基础篇 中有系统定义原地修改不申请额外存储空间只利用原存储空间完成操作空间复杂度运行完一个算法所需的内存大小本题要求 O(1)。二、题目描述与示例给定一个排序数组你需要在原地删除重复出现的元素使得每个元素最多出现两次返回移除后数组的新长度。不要使用额外的数组空间你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。示例 1给定 nums [1,1,1,2,2,3], 函数应返回新长度 length 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。示例 2给定 nums [0,0,1,1,1,1,2,3,3], 函数应返回新长度 length 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面的元素。注原文档示例 2 中前五个元素为笔误实际返回长度为 7应修改前 7 个元素。两个示例共同透露两个关键约束返回值是整数新长度但判题系统会根据该长度打印数组前len个元素——所以前len个位置必须已经被整理为合法结果超出新长度的尾部元素无需清理这为覆盖写入而不是删除元素提供了合法性依据。三、说明为什么返回整数输出却是数组原文档给出了官方说明的核心逻辑这里完整保留并展开为什么返回数值是整数但输出的答案是数组呢请注意输入数组是以**引用**方式传递的这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下// nums 是以引用方式传递的。也就是说不对实参做任何拷贝 int len removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i 0; i len; i) { print(nums[i]); }理解这一点对面试表达很重要本题的答案由两部分构成——函数返回值新长度 被原地改写后的数组前段内容。判题系统先用返回的len界定打印范围再按范围打印元素二者缺一不可。这也是为什么许多候选人在 LeetCode 上写复制一份新数组再返回会直接超空间题目要求的就是修改原数组而不是生成新数组。四、解法一快慢指针覆盖法原文档解法逐行精讲原文档给出的解法非常精简参考了评论区大佬的思路直接贴出并逐行拆解int removeDuplicates(vectorint nums) { int len 0; for (int i 0; i nums.size(); i) { if (len 2 || nums[i] ! nums[len-2]) nums[len] nums[i]; } return len; }4.1 变量含义原文档详解完整继承len表示删除重复元素后新序列的长度同时也表示新元素进入新序列的写入索引——它正是慢指针i是循环变量用于遍历整个旧序列——它正是快指针if (len 2) nums[len] nums[i];如果新序列的长度小于 2即新序列中不会存在两个相同的元素此时i位置所在元素不可能与新序列构成三个重复直接将新元素加入新序列并更新长度if (nums[i] ! nums[len-2]) nums[len] nums[i];nums[len-2]直接取新序列中倒数第二个元素。若它与新元素相同说明加入后会产生 3 个相同元素违反最多出现两次的题意故舍弃若不同则安全写入题意只要求新序列紧挨在一起即可多出的长度不参与评测。4.2 为什么用nums[len-2]而不是nums[len-1]这是本题最值得咀嚼的细节也是面试官常追问的点若只比较nums[i] ! nums[len-1]能拦截的只是与前一个元素相同的情况只能保证最多出现一次——那是 26 题的判定逻辑本题允许出现两次因此需要把窗口再拉长一位检查新序列倒数第二个元素。只要新元素与nums[len-2]不同无论它与nums[len-1]是否相同最多和倒数第一个相同都不会造成三个连续相同元素。换句话说len永远指向下一个可写位置而nums[len-2]恰好是有效区间末尾往前数第二位用它做参照天然把每个元素的保留上限卡死在 2 次。4.3 手推一遍示例 1以nums [1,1,1,2,2,3]为例逐步跟踪步骤inums[i]len条件判断动作1010len2成立nums[0]1len12111len2成立nums[1]1len23212nums[2]!nums[0]? 1!1 不成立跳过第 3 个 1 被丢弃4322nums[3]!nums[0]? 2!1 成立nums[2]2len35423nums[4]!nums[1]? 2!1 成立nums[3]2len46534nums[5]!nums[2]? 3!2 成立nums[4]3len5最终返回len 5数组前 5 位为[1,1,2,2,3]与题目示例完全一致。可见快指针i读、慢指针len写二者速度不同是标准的快慢指针读写指针模型。五、复杂度与正确性分析时间复杂度 O(n)i一趟扫描整个数组循环体内是常数次比较与赋值总操作次数与n nums.size()成正比空间复杂度 O(1)只使用了一个整型变量len不申请任何与 n 相关的辅助数组完全符合题目原地 O(1) 额外空间的硬性要求正确性len维护的始终是已处理区间中满足每个元素最多出现两次的前缀通过数学归纳可知每一步写入都不会破坏该不变式因此最终前缀即答案。值得说明的是原文档记录了作者当时的提交数据执行用时 12 ms在所有 cpp 提交中击败了 98.85% 的用户内存消耗 8.9 MB击败了 73.46% 的用户。该数据属于特定提交环境下的历史记录可作为参考但不应作为跨平台、跨版本的普适结论。六、举一反三推广到每个元素最多保留 k 个把判定条件中的常量 2 抽象为参数k即可得到本题的通式解法int removeDuplicatesK(vectorint nums, int k) { int len 0; for (int i 0; i nums.size(); i) { if (len k || nums[i] ! nums[len - k]) nums[len] nums[i]; } return len; }k 1时退化为 LeetCode 26 题「删除排序数组中的重复项」每个元素最多一次k 2时即本题 80 题任意k下核心思想不变只要新元素与有效区间倒数第 k 个元素不同就允许写入。面试中遇到此类题可以先讲通式再代入 k1/k2往往比直接背代码更显功底。作为对照练习InterviewGuide 双指针分类下还有 532. 数组中的 K-diff 数对、75. 颜色分类荷兰国旗问题、986. 区间列表的交集 等同样考察双指针思想的题目刷完本题后建议按序列继续巩固。七、边界情况与易错点小结空数组与单元素数组len 2分支直接兜底空数组返回 0、单元素返回 1无需特判len-2的越界风险仅在len 2时才会走到nums[i] ! nums[len-2]分支因为||短路所以len-2 0恒成立索引安全——这正是先判断len 2这一写法的精妙之处不要用erase逐个删除vector 中间删除是 O(n) 的最坏会退化为 O(n²)且同样破坏原地语义覆盖写入才是本题最优姿势返回值与数组前段要配套只返回长度而忘记改写前len个元素或者改了但返回错误的长度都会导致评测失败输入必须是已排序数组题目前提是排序数组若输入无序解法不成立需先排序再套用InterviewGuide 在 十大排序 系列中整理了常用排序实现可供参考。八、总结LeetCode 80 题的核心价值不在于背下三行代码而在于它浓缩了三个面试高频考点引用传递与原地修改理解返回值 被改写数组共同构成答案是很多企业笔试环境如 ACM 式函数签名下必须掌握的意识快慢指针思想i读、len写一趟扫描完成去重是数组类原地算法的通用范式通过倒数第 k 个元素控制保留上限把 26 题与 80 题统一到同一套通式面对最多保留 m 个的任意变体都能立即迁移。本文对应的原始题解记录位于 80.删除排序数组中的重复项II.md刷题过程中建议结合 InterviewGuide 的 双指针专题目录 系统规划把这一题当作原地去重系列的地基理解透了后续字符串去重、流式去重等变体都会迎刃而解。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐0080. 删除有序数组中的重复项 IILeetCode 题解有序数组最多保留两个的原地去重快慢指针进阶0080. 删除有序数组中的重复项 IILeetCode 题解有序数组最多保留两个的原地去重快慢指针进阶 本篇是「算法通关手册」AlgoNote 中教程文档知识库LeetCode 26. 删除排序数组中的重复项快慢指针读写指针原地去重题解LeetCode 26. 删除排序数组中的重复项快慢指针读写指针原地去重题解 本文以 leetcode 题解仓库 gh_mirrors/le/leetc文档教程知识库LeetCode-Go 题解 80Remove Duplicates from Sorted Array II 有序数组去重最多保留两个的双指针实现LeetCode Go 题解 80Remove Duplicates from Sorted Array II 有序数组去重最多保留两个的双指针实现 导读示例工程上一篇华为昇腾HCCL实战教程5个AllReduce应用场景完整代码示例 下一篇Qwen3-VL-235B-A22B-Thinking2025最强开源多模态大模型技术突破与行业变革创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考