示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文以 doocs/leetcode 仓库中 0080.Remove Duplicates from Sorted Array II 题解 为核心系统讲解 LeetCode 80 号题删除有序数组中的重复项 II的题意、判题机制、一次遍历双指针解法及其正确性并延伸到最多保留 k 个相同元素的通用模板结合仓库内 Python、Java、C、Go、TypeScript、Rust、JavaScript、C# 八种语言的真实源码逐一定位分析。读完本文你将掌握一类有序数组原地去重问题的统一解法并能直接套用到 LeetCode 26 等相似题目上。一、题目理解在有序数组中只留两次题目原文摘自 README_EN.md给定一个按非递减顺序non-decreasing order排列的整数数组nums请你原地in-place删除重复元素使得每个唯一元素最多出现两次且保持元素相对顺序不变。由于部分语言无法改变数组长度结果必须放在nums数组的前部。更形式化地说若去重后剩余k个元素则nums的前k个位置应存放最终结果前k个元素之后的内容无关紧要。函数返回k即结果长度。整个操作不允许为另一个数组分配额外空间必须通过修改输入数组完成额外内存为O(1)。题目给出的判题机制Custom Judge判题器会使用如下代码验证你的实现int[] nums [...]; // Input array int[] expectedNums [...]; // The expected answer with correct length int k removeDuplicates(nums); // Calls your implementation assert k expectedNums.length; for (int i 0; i k; i) { assert nums[i] expectedNums[i]; }只要所有断言通过你的解法即被视为接受accepted。这带来两个关键约束必须原地修改返回值k与数组前k个元素共同构成答案前k个元素之后残留什么数据都无所谓示例中以_表示。约束条件1 nums.length 3 * 10^4-10^4 nums[i] 10^4nums已按非递减顺序排列二、示例推演先看输出长什么样示例 1输入nums [1,1,1,2,2,3] 输出5, nums [1,1,2,2,3,_]解释函数返回k 5前五个元素为1, 1, 2, 2, 3。原数组中有三个1只能保留两个k之后的位置_内容不限。示例 2输入nums [0,0,1,1,1,1,2,3,3] 输出7, nums [0,0,1,1,2,3,3,_,_]解释函数返回k 7前七个元素为0, 0, 1, 1, 2, 3, 3。四个连续的1被压缩为两个其余元素按原相对顺序保留。两个示例共同揭示解题要点相同值在有序数组中必然相邻连续成段因此判断当前值能否保留不需要全局查找只需与已保留序列中的特定位置比较即可。三、朴素思路为什么不行最容易想到的方案是另开一个新数组每个值最多抄写两次最后再拷贝回nums。这从结果上看是正确的但违背题目的核心限制——必须原地修改、额外空间 O(1)。这也是 README_EN.md 中思考部分首先排除的路线n 3 * 10^4的规模下正确性没问题但空间上不合格正确做法应当一趟完成。四、核心解法一次遍历写入指针 k4.1 算法思想与 LeetCode 26每个唯一值保留一次相比本题保留至多两次。设k为已保留前缀的长度同时它也是下一个写入位置即慢指针遍历指针i是快指针初始k 0表示空数组从左到右遍历每个元素x若k 2或x ! nums[k - 2]说明x可以保留要么是前两个元素要么它与已保留序列的倒数第二个不同因此不会出现第三次把x写入nums[k]然后k自增 1否则x与nums[k - 2]相同意味着它已经是第三个或更多相同值直接跳过。遍历结束后nums的前k个元素即答案k即答案长度。为什么与nums[k-2]比较而不是nums[k-1]因为保留上限是 2nums[k-2]是已保留序列中倒数第二个元素。若当前x等于它说明x已是第三个相同值若不同则最多只能凑出两个相同值必然合法。这正是从26 题比较nums[k-1]到80 题比较nums[k-2]的推广——保留上限从 1 变成 2比较位置就后退一位。4.2 逐步走查示例以nums [1,1,1,2,2,3]为例步骤遍历元素 xk判断写入后 nums 前缀k 更新0–0–[]0110k2保留[1]1211k2保留[1,1]2312x nums[0]1跳过[1,1]2422x ! nums[0]1保留[1,1,2]3523x ! nums[1]1保留[1,1,2,2]4634x ! nums[2]2保留[1,1,2,2,3]5最终返回k 5与示例 1 完全一致。注意写入始终发生在nums[k]而k i所以写入位置不会覆盖尚未遍历的元素原地操作安全。4.3 正确性要点有序性保证同值相邻这是比较nums[k-2]就能拦截第三个重复值的前提若数组无序该比较会失效不变式遍历过程中nums[0..k-1]始终是每个元素最多出现两次、相对顺序与原数组一致的合法前缀贪心正确每个可保留的值都在最早可写入的位置写入不会漏掉任何应保留的元素复杂度单趟扫描时间O(n)仅用常数个变量空间O(1)n为数组长度。五、多语言实现仓库源码逐一定位doocs/leetcode 仓库为该题提供了 8 种语言的实现全部遵循同一套写入指针 k模板代码文件位于 0080.Remove Duplicates from Sorted Array II 目录Python3Solution.pyclass Solution: def removeDuplicates(self, nums: List[int]) - int: k 0 for x in nums: if k 2 or x ! nums[k - 2]: nums[k] x k 1 return kJavaSolution.javaclass Solution { public int removeDuplicates(int[] nums) { int k 0; for (int x : nums) { if (k 2 || x ! nums[k - 2]) { nums[k] x; } } return k; } }CSolution.cppclass Solution { public: int removeDuplicates(vectorint nums) { int k 0; for (int x : nums) { if (k 2 || x ! nums[k - 2]) { nums[k] x; } } return k; } };GoSolution.gofunc removeDuplicates(nums []int) int { k : 0 for _, x : range nums { if k 2 || x ! nums[k-2] { nums[k] x k } } return k }TypeScriptSolution.tsfunction removeDuplicates(nums: number[]): number { let k 0; for (const x of nums) { if (k 2 || x ! nums[k - 2]) { nums[k] x; } } return k; }RustSolution.rsimpl Solution { pub fn remove_duplicates(nums: mut Veci32) - i32 { let mut k 0; for i in 0..nums.len() { if k 2 || nums[i] ! nums[k - 2] { nums[k] nums[i]; k 1; } } k as i32 } }JavaScriptSolution.js/** * param {number[]} nums * return {number} */ var removeDuplicates function (nums) { let k 0; for (const x of nums) { if (k 2 || x ! nums[k - 2]) { nums[k] x; } } return k; };C#Solution.cspublic class Solution { public int RemoveDuplicates(int[] nums) { int k 0; foreach (int x in nums) { if (k 2 || x ! nums[k - 2]) { nums[k] x; } } return k; } }从源码结构看各语言实现的核心差异仅在语法层Rust 因借用检查需显式用下标访问、Go 的for range、C# 的foreach算法骨架完全一致一个变量k同时充当写入指针与结果长度这也是该解法可读性极佳、易于跨语言移植的原因。六、扩展推广到最多保留 k 个相同元素原题限定相同数字最多出现 2 次但题解文档给出了更强的通用结论——可以扩展到最多保留 k 个相同数字由于相同数字最多保留k个原数组的前k个元素可以直接保留对于后续数字能够保留的前提是当前数字x与已保留数字中倒数第k个比较不同则保留相同则跳过。由此得到通用模板以 Python 为例class Solution: def removeDuplicates(self, nums: List[int]) - int: k 2 # 可改为任意保留上限 for x in nums: if k 2 or x ! nums[k - 2]: nums[k] x k 1 return k对应地当保留上限为 1 时只需把比较对象换成nums[k - 1]就退化成了 LeetCode 26 的解法见下文。这一推广的本质是有序数组中只需检查倒数第 k 个已保留元素即可判断当前值是否会造成第 k1 次重复与相同值的具体出现次数无关。七、与相似题目 26 的对比题解文档将 26. Remove Duplicates from Sorted Array 列为相似题目。两题的对比如下对比维度26. 删除有序数组中的重复项80. 删除有序数组中的重复项 II难度简单Easy中等Medium保留上限每个唯一值出现 1 次每个唯一值出现至多 2 次判定条件k 0或x ! nums[k - 1]k 2或x ! nums[k - 2]核心思路写入指针 k与最后一位比较写入指针 k与倒数第二位比较26 题的解法同样可以在 0026.Remove Duplicates from Sorted Array 题解 中查看完整多语言实现。可以看到两题共用同一套双指针框架唯一区别是比较窗口的长度——保留上限为 1 时比较nums[k-1]保留上限为 2 时比较nums[k-2]。掌握这一点遇到最多保留 3 个最多保留任意个的变体时即可举一反三。八、总结题型定位有序数组 原地去重 O(1) 额外空间属于典型的**双指针快慢指针**问题标签为Array、Two Pointers核心技巧用单个变量k兼任写入指针与结果长度利用有序性用x ! nums[k-2]拦截第三个重复值复杂度时间 O(n)空间 O(1)满足n 3 * 10^4的数据规模实战要点先保留前 2 个元素作为种子k 2分支再对后续元素执行与倒数第 2 个比较的判定写入恒在nums[k]且k i不会破坏尚未遍历的数据延伸能力同一模板可推广到最多保留 k 个通用情形并与 LeetCode 26 形成完整的方法论闭环。如需查看该题完整的中英文题解、判题说明与全部语言实现可直接阅读仓库中的 README.md中文与 README_EN.md英文。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 26「删除有序数组中的重复项」题解双指针单次遍历原地去重doocs/leetcode 多语言实现LeetCode 26「删除有序数组中的重复项」题解双指针单次遍历原地去重doocs/leetcode 多语言实现 导读 本文以 doocs/leetco示例工程0080. 删除有序数组中的重复项 IILeetCode 题解有序数组最多保留两个的原地去重快慢指针进阶0080. 删除有序数组中的重复项 IILeetCode 题解有序数组最多保留两个的原地去重快慢指针进阶 本篇是「算法通关手册」AlgoNote 中教程教育LogicStack-LeetCode 题解80. 删除有序数组中的重复项 II —— 双指针与「保留 k 位」通解实战LogicStack LeetCode 题解80. 删除有序数组中的重复项 II —— 双指针与「保留 k 位」通解实战 本篇技术指南以「宫水三叶的刷题日记」教程文档上一篇如何快速提取 Unity 游戏资源AssetRipper 上手实践下一篇从2.0到最新版Duplicati无缝升级指南与避坑手册创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考