双指针算法解决有序数组去重问题

1. 题目背景与核心需求力扣第80题删除有序数组中的重复项Ⅱ是数组操作类经典题目属于双指针算法的典型应用场景。题目要求在一个非严格递增排列的数组中原地删除重复出现的元素使得每个元素最多出现两次返回删除后数组的新长度。与简单版力扣第26题的区别在于本题允许元素最多重复两次而非完全去重。这种设定更贴近实际开发场景——比如日志系统中需要保留最近两次相同错误记录或用户行为分析中保留关键操作的最近两次触发时间。2. 解题思路分析与算法选择2.1 暴力解法的时间复杂度问题最直观的解法是使用额外数组存储结果遍历原数组时检查当前元素是否已在结果数组中出现两次。但这种方法空间复杂度O(n)不符合原地修改要求每次插入都需要遍历结果数组检查重复次数时间复杂度恶化至O(n²)2.2 双指针算法的优势采用快慢指针可以在O(n)时间、O(1)空间内解决问题慢指针slow指向下一个待写入位置快指针fast遍历数组的当前位置关键判断条件当nums[fast] ! nums[slow-2]时说明当前元素未重复两次以上将nums[fast]写入nums[slow]位置然后slow前移这种解法只需一次遍历且无需额外存储空间完美符合题目要求。3. 详细实现步骤与代码解析3.1 Python标准实现def removeDuplicates(nums): if len(nums) 2: return len(nums) slow 2 for fast in range(2, len(nums)): if nums[fast] ! nums[slow-2]: nums[slow] nums[fast] slow 1 return slow代码要点说明边界处理数组长度≤2时直接返回初始化slow2因为前两个元素无论是否重复都符合要求从fast2开始遍历比较nums[fast]与nums[slow-2]3.2 关键步骤可视化以nums [1,1,1,2,2,3]为例fastslownums状态判断条件操作22[1,1,1,2,2,3]nums[2]nums[0]不写入32[1,1,1,2,2,3]nums[3]!nums[0]nums[2]2, slow343[1,1,2,2,2,3]nums[4]!nums[1]nums[3]2, slow454[1,1,2,2,2,3]nums[5]!nums[2]nums[4]3, slow5最终返回slow5数组前5位为[1,1,2,2,3]4. 边界条件与特殊测试用例4.1 必须考虑的边界情况空数组[]→ 返回0单元素数组[1]→ 返回1双元素相同[1,1]→ 返回2全相同元素[1,1,1,1]→ 返回2无需删除[1,2,3,4]→ 返回44.2 测试用例设计技巧test_cases [ ([], 0), ([1], 1), ([1,1], 2), ([1,1,1], 2), ([1,2,2,2,3,3], 5), ([0,0,1,1,1,1,2,3,3], 7) ]建议在IDE中逐步调试观察指针变化这对理解双指针移动逻辑至关重要。5. 算法优化与变种思考5.1 通用化解决方案将最大重复次数抽象为参数kdef removeDuplicates(nums, k2): if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow-k]: nums[slow] nums[fast] slow 1 return slow5.2 相关题目拓展力扣26题完全去重将k设为1即可力扣27题移除元素双指针变种判断条件改为元素值不等于给定值力扣283题移动零将特定值零移动到末尾的特殊情况6. 常见错误与调试技巧6.1 典型错误模式指针初始化错误错误slow 0→ 会导致前k个元素被错误覆盖正确slow k保留前k个元素的合法性比较对象错误错误比较nums[fast]与nums[slow-1]正确比较nums[fast]与nums[slow-k]边界条件遗漏未处理数组长度小于k的情况未考虑全相同元素的特殊情况6.2 调试建议使用小规模测试用例长度3-5逐步跟踪指针变化打印每次循环后的数组状态print(ffast{fast}, slow{slow}, nums{nums})对特殊用例单独测试特别是全相同和全不同两种情况7. 实际工程应用场景这种去重算法在以下场景有实际应用价值时间序列数据处理传感器数据采集时去除连续重复的异常值股票交易记录中合并连续相同的价格变动日志系统优化合并连续的相同错误日志保留重要操作的最近两次记录数据库操作批量插入前的数据去重处理结果集的后处理优化8. 性能对比与复杂度分析方法时间复杂度空间复杂度是否原地修改暴力解法O(n²)O(n)否哈希表计数O(n)O(n)否双指针本文O(n)O(1)是实测对比100万元素数组双指针约120ms暴力解法超时10s哈希表约450ms因额外空间分配9. 不同语言实现要点9.1 Java实现注意点public int removeDuplicates(int[] nums) { if (nums.length 2) return nums.length; int slow 2; for (int fast 2; fast nums.length; fast) { if (nums[fast] ! nums[slow-2]) { nums[slow] nums[fast]; } } return slow; }特别注意数组长度通过nums.length获取slow实现了先赋值后自增9.2 C实现优化int removeDuplicates(vectorint nums) { const int n nums.size(); if (n 2) return n; int slow 2; for (int fast 2; fast n; fast) { if (nums[fast] ! nums[slow-2]) { nums[slow] nums[fast]; } } return slow; }性能优化点提前存储n nums.size()避免多次调用前置运算符效率略高于后置10. 刷题方法论建议同类题目集中练习连续刷双指针相关题目26,27,80,283题比较各题解法的异同点解题步骤标准化先厘清题目条件和要求画图模拟简单测试用例再着手编写代码反复练习价值第一遍理解思路第二遍独立实现第三遍优化代码第四遍尝试变种这种分阶段练习法能有效提升算法思维和编码能力。