双指针算法实战：LeetCode有序数组去重解析

1. 问题背景与核心需求

这道题目来自LeetCode面试经典150题系列，题目编号26，要求我们处理一个已排序的数组，原地删除重复出现的元素，使每个元素只出现一次，并返回新数组的长度。这类数组操作题在技术面试中出现频率极高，据不完全统计，在字节跳动、腾讯等大厂的初级算法面试中出现概率超过60%。

为什么面试官如此钟爱这道题？因为它完美考察了三个核心能力：

• 对数组数据结构的基础操作熟练度
• 双指针算法的理解和应用能力
• 边界条件处理的严谨性

在实际工程中，类似场景比比皆是。比如处理有序的日志数据时去除重复条目，或者清洗用户行为数据中的重复记录。这道题给出的解决方案可以直接迁移到这些真实业务场景中。

2. 暴力解法与空间复杂度分析

我们先看最直观的解法：使用额外空间。创建一个新数组，遍历原数组时将不重复的元素依次放入。这种方法时间复杂度O(n)，但空间复杂度也是O(n)，不符合题目"原地修改"的要求。

def removeDuplicates(nums): if not nums: return 0 unique_nums = [nums[0]] for i in range(1, len(nums)): if nums[i] != nums[i-1]: unique_nums.append(nums[i]) nums[:len(unique_nums)] = unique_nums return len(unique_nums)

这个解法虽然能通过测试，但在面试中会被追问优化空间。面试官期望的解法空间复杂度应该是O(1)，也就是不使用额外数组。

3. 双指针算法精解

3.1 快慢指针实现原理

正确的解法是使用双指针技术，具体步骤如下：

1. 初始化慢指针slow=0，快指针fast=1
2. 遍历数组，当nums[fast] ≠ nums[slow]时：
   • 先移动slow指针：slow += 1
   • 然后将nums[fast]的值赋给nums[slow]
3. 最后返回slow+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 + 1

这个算法之所以高效，是因为它利用了数组已排序的特性。当遇到重复元素时，快指针继续前进，直到找到不重复的元素才进行赋值操作。

3.2 时间复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组
• 空间复杂度：O(1)，只使用了常数级别的额外空间

4. 边界条件与特殊案例处理

在实际编码和面试中，以下几个边界情况需要特别注意：

1. 空数组输入：直接返回0
2. 单元素数组：无需处理，直接返回1
3. 全相同元素数组：应返回1
4. 超大数组测试：验证算法效率

# 边界测试案例 print(removeDuplicates([])) # 输出：0 print(removeDuplicates([1])) # 输出：1 print(removeDuplicates([1,1,1])) # 输出：1 print(removeDuplicates([1,2,2,3])) # 输出：3

5. 算法优化与变种问题

5.1 通用解法模板

我们可以将这个解法抽象成一个模板，适用于大多数有序数组去重问题：

def removeDuplicatesTemplate(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 + 1

5.2 相关变种题目

掌握这个模板后，可以轻松解决以下变种问题：

1. 删除排序数组中的重复项II（允许最多出现两次）
2. 移动零（将0移到数组末尾）
3. 移除元素（删除所有等于某个值的元素）

以"删除排序数组中的重复项II"为例，只需稍作修改：

def removeDuplicatesII(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

6. 实际工程应用场景

这个算法在真实业务中有广泛的应用价值：

1. 日志处理：去除重复的日志条目
2. 用户行为分析：清洗重复的点击事件
3. 数据库优化：压缩存储重复数据
4. 时间序列数据处理：去除重复的时间戳

例如处理用户搜索日志时：

# 原始日志数据：[时间戳, 用户ID, 搜索词] search_logs = [ [1630000000, "user1", "python"], [1630000001, "user1", "python"], [1630000002, "user1", "java"], # ...更多日志 ] # 去除连续相同的搜索记录 cleaned_logs = [search_logs[0]] for log in search_logs[1:]: if log[2] != cleaned_logs[-1][2]: cleaned_logs.append(log)

7. 面试技巧与注意事项

在面试中回答这类问题时，建议采用以下步骤：

1. 明确问题：确认输入输出要求、边界条件
2. 提出暴力解法：先给出简单方案，再优化
3. 分析复杂度：说明时间/空间复杂度
4. 优化方案：引入双指针等优化手段
5. 编写代码：注意变量命名和代码风格
6. 测试案例：覆盖各种边界情况

常见面试陷阱：

• 忘记处理空数组情况
• 返回长度错误（应该是slow+1而不是slow）
• 修改了数组但忘记返回长度

8. 刷题建议与学习路径

对于想系统提升算法能力的开发者，建议：

1. 先掌握基础：数组、链表、哈希表等数据结构
2. 学习算法模板：双指针、滑动窗口、DFS/BFS等
3. 按专题练习：LeetCode热题100、剑指Offer等
4. 参加周赛：LeetCode每周竞赛提升实战能力
5. 总结归纳：建立自己的解题模板库

推荐的学习资源：

• 《剑指Offer》经典面试题解析
• LeetCode官方出品的《面试经典150题》
• 各大厂真题精选合集

最后分享一个实用技巧：在解决数组问题时，先在纸上画出指针移动示意图，往往能帮助快速找到解题思路。对于这道题，画出快慢指针在不同情况下的位置变化，可以直观理解算法的工作原理。