InterviewGuide 力扣刷题笔记：80. 删除排序数组中的重复项 II——原地去重的双指针通用解法

文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文是《InterviewGuide》精选力扣 300 道算法题系列中“双指针”标签下的一道 Medium 题解。围绕阿秀刷题笔记中的原始解法从题目约束、引用传递机制、代码逐行拆解到复杂度论证讲透“有序数组原地去重、每个元素最多保留两次”这一经典套路并推广出可复用的“最多保留 k 次”通用模板帮助你从容应对面试中的同族变体题。题目回顾LeetCode 80. 删除排序数组中的重复项 II给定一个排序数组你需要在原地删除重复出现的元素使得每个元素最多出现两次返回移除后数组的新长度。不要使用额外的数组空间你必须在原地修改输入数组并在使用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 。 你不需要考虑数组中超出新长度后面的元素。原笔记将其标注为“很好的题目”原因在于它表面是“删除重复元素”的简单任务实则隐藏着双指针压缩、条件后移这两大高频面试考点是 LeetCode 26. 删除排序数组中的重复项每个元素最多保留一次的升级版。为什么返回的是整数输出的却是数组题目说明中特别强调输入数组是以“引用”方式传递的这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下// nums 是以引用方式传递的。也就是说不对实参做任何拷贝 int len removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i 0; i len; i) { print(nums[i]); }这正是“原地in-place算法”的评测惯例判题系统不关心数组尾部残留的旧数据只按你返回的len截取前len个元素进行校验。因此解题时只需保证新序列紧挨在数组头部超出新长度的部分可以任意残留无需真正删除或缩容。核心思路一个“写指针”完成的原地压缩对于已经排好序的数组相同元素必然连续成段。要让每个元素最多出现两次等价于扫描整个数组时只要当前位置的元素不与“已保留序列中倒数第二个元素”相同就可以安全地把它写入新序列的尾部。这样整个数组只被扫描一遍且就地写入不需要开辟任何辅助数组天然满足 O(1) 额外空间的要求。从实现形态上看这属于双指针思想中“快慢指针”的变体——i是快指针只读扫描len是慢指针写位置两者共用同一个数组。第一版解法阿秀原解简洁到极致的双指针原笔记给出的解法很短执行用时 12 ms、内存消耗 8.9 MB作者当时在 C 提交中的记录分别击败约 98.85% 与 73.46% 的用户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; }原笔记参考了评论区大佬的解法下面把各个步骤和变量的含义完整展开len表示的是删除重复元素后新序列的长度同时也表示新元素进入新序列的索引即下一个写入位置i就是循环变量用于遍历整个旧序列if (len 2) nums[len] nums[i];的意思是如果新序列的长度小于 2即新序列中不会存在两个相同的元素此时i位置所在元素不可能与新序列中已有的两个元素构成三个相同元素直接将新元素加入到新序列中并更新新序列的长度if (nums[i] ! nums[len-2]) nums[len] nums[i];的意思是如果新元素加入后不会和前两个元素构成 3 个相同的元素nums[len-2]就是直接取新序列中倒数第二个元素如果该元素和新元素相同说明加入后会构成 3 个相同的元素显然不符合题意就将新元素加入到新序列中并更新新序列的长度题意只要求将新序列紧挨在一起就行多出的长度将不参与评测。正确性论证为什么这样写必然成立可以分三步论证这段代码的正确性前两个元素无条件保留。len 2时直接写入保证新序列长度至少为 2 前不受任何限制。因为一个元素出现两次总是被允许的前两个元素无论相同与否都必然合法。从第三个元素起只需与“倒数第二个”比较。由于数组有序且已保留的新序列同样有序若nums[i]与nums[len-2]相同则它必然也与nums[len-1]相同中间夹着的元素只可能是同一个值此时再写入就会形成 3 连重复必须丢弃反之若与nums[len-2]不同则无论与nums[len-1]是否相同最多只会形成 2 连重复写入后依然合法。写入位置len单调不减且永远不会越过读取位置i写入量 ≤ 读取量因此覆盖操作是安全的不会破坏后续待读取的数据。复杂度分析时间复杂度O(n)。整个数组只被for循环扫描一遍每次迭代仅做常数次比较与赋值其中 n 为数组长度空间复杂度O(1)。全程没有申请与 n 相关的辅助存储仅使用了len、i两个整型变量满足题目“不要使用额外的数组空间”的硬性约束。这正是面试官期待的最优解一趟扫描 常数空间无法再被优化。推广把“最多两次”泛化成“最多 k 次”从上面的正确性论证可以看出比较基准nums[len-2]中的数字 2 正是题目允许的最大重复次数。把它替换成任意常数k就得到“每个元素最多保留 k 次”的通用模板int removeDuplicates(vectorint nums, int k) { // k 2 即本题 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时即本题。面试中只要讲清“为什么是与len-k位置比较”这一句就能向面试官证明你吃透了这族题目的本质而不是死记硬背代码。从源码到面试本专题的延伸阅读本题收录于 InterviewGuide 仓库的 双指针专题目录Medium 分组聚合版题解可见 total/08-双指针/medium/medium.md同一专题下的 75. 颜色分类 同样是原地修改数组的代表题其“第二版”用到了双路快排的思想可与本题对照学习若想系统补齐数组原地操作与双指针的其他形态相向指针、滑动窗口等可先阅读仓库的 算法基础部分再按 力扣刷题笔记专栏说明 中的 13 个标签逐个击破。面试中遇到本题时建议按“题目约束 → 有序性利用 → 写指针压缩 → 泛化到 k 次”这条链路作答先说思路再写代码最后补上复杂度分析即可构成一次完整、扎实的算法面试回答。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐LeetCode 26. 删除排序数组中的重复项快慢指针读写指针原地去重题解LeetCode 26. 删除排序数组中的重复项快慢指针读写指针原地去重题解 本文以 leetcode 题解仓库 gh_mirrors/le/leetc文档教程知识库LogicStack-LeetCode 题解80. 删除有序数组中的重复项 II —— 双指针与「保留 k 位」通解实战LogicStack LeetCode 题解80. 删除有序数组中的重复项 II —— 双指针与「保留 k 位」通解实战 本篇技术指南以「宫水三叶的刷题日记」教程文档YCBlogs 算法笔记排序数组原地去重LeetCode 26的双指针实现与复杂度分析YCBlogs 算法笔记排序数组原地去重LeetCode 26的双指针实现与复杂度分析 本篇基于 YCBlogs 仓库中 从数组中删除重复项 https:教程技术博客文档创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考