删除排序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

思路

双指针算法。
采用fast和slow双指针，fast指针用于完整遍历整个输入数组，slow指针用于初始化最后处理之后的数组,标志下一个待插入元素的位置。

初始化新数组时机：fast指针遍历数组时遇到新的数字

终止标志：fast指针遍历完数组

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int L = nums.size();
        if(L <= 0){              //处理数组为空的情况
            return 0;
        }       
        int fast = 1 ;   //快指针
        int slow = 1 ;   //慢指针
        while(fast < L){ //终止标志
            if(nums[fast] != nums[fast-1])
                nums[slow] = nums[fast], slow++;  //只有在遇到新元素时，慢指针才移动。slow等于新数组大小。   
            fast++; //快指针不断移动
        }
        return slow; //先初始化，后slow++，所以返回的时slow，而非slow+1；
    }
};

复杂度分析

时间复杂度：O(n) 快慢指针最多都移动n次。

空间复杂度：O(1),使用常数的额外空间。