题目描述

给定一个升序排列的数组 nums，要求原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。要求空间复杂度为 O(1)，即不使用额外数组空间。

解题思路

双指针法是解决此类问题的经典方法。通过维护两个指针（快指针和慢指针），可以在一次遍历中完成去重操作。快指针用于遍历数组，慢指针用于指向当前不重复元素的末尾。

实现步骤

初始化慢指针 slow 为 0，快指针 fast 从 1 开始遍历数组。

比较 nums[fast] 和 nums[slow]，如果两者不相等，说明遇到新元素，将 slow 右移一位，并将 nums[fast] 的值赋给 nums[slow]。

重复上述过程直到快指针遍历完整个数组，最终 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

复杂度分析

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

边界情况

• 空数组：直接返回 0。
• 所有元素相同：慢指针不会移动，最终长度为 1。
• 无重复元素：慢指针与快指针同步移动，最终长度为原数组长度。

示例

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5，且原数组前 5 个元素修改为 [0,1,2,3,4]。

扩展思考

此方法适用于有序数组的去重。若数组无序，需先排序（时间复杂度 O(n log n)），再使用双指针法。对于允许重复最多 k 次的问题，可通过调整慢指针的移动条件来扩展解法。