双指针技巧实现数组原地去重：LeetCode经典解法

1. 题目背景与核心需求这道题目来自力扣(LeetCode)的面试经典150题系列要求对已排序数组进行原地(in-place)去重操作。在实际编程面试中数组操作类题目出现频率高达35%而双指针技巧的应用占比超过60%。题目看似简单却考察了三个关键能力对数组内存布局的理解、双指针算法的灵活运用以及边界条件的处理能力。注意面试官通常会追问时间复杂度和空间复杂度的计算过程以及为什么选择这种解法而不是其他方法。2. 解法思路与算法选择2.1 暴力解法分析最直观的方法是使用额外数组存储唯一元素空间复杂度O(n)。但题目要求原地修改这就需要更巧妙的处理方式。2.2 双指针最优解采用快慢指针技巧慢指针slow标记唯一序列的末尾快指针fast遍历整个数组当nums[fast] ≠ nums[slow]时将nums[fast]赋值给nums[slow1]然后slow前进。这种解法时间复杂度O(n)空间复杂度O(1)完美符合题目要求。def removeDuplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 13. 关键实现细节与调试技巧3.1 边界条件处理空数组情况直接返回0单元素数组无需处理直接返回1全相同元素数组只需返回13.2 指针移动逻辑慢指针只有在发现新元素时才移动这保证了它始终指向当前唯一序列的末尾。实测发现将判断条件改为nums[fast] nums[slow]可以应对非严格递增的情况。4. 复杂度分析与优化空间4.1 时间复杂度证明快指针完整遍历数组一次时间复杂度严格为O(n)。通过leetcode的耗时统计可以看到对于百万级数据量执行时间仍保持在毫秒级。4.2 空间复杂度优势相比使用集合(set)去重需要O(n)空间该算法仅用常数空间在内存受限的场景(如嵌入式系统)特别有价值。5. 实际面试中的变体问题面试官可能提出的进阶问题包括如果允许最多保留2个重复项如何修改对未排序数组该如何处理如何用函数式编程实现相同功能对于问题1只需增加一个计数器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 slow6. 刷题建议与学习路径建议按照以下顺序掌握数组类题目双指针基础删除重复项、移动零滑动窗口最小覆盖子串多指针处理三数之和特殊技巧接雨水问题对于准备面试的同学建议每天保持3-5道同类题目的训练量重点记录每种解法的适用场景和时间/空间复杂度。