26.删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104-
nums已按 升序 排列
思路：
本题也是经典的双指针算法题，对于一个数组来说，删除一个元素是比较复杂的，每次删除元素后，若要保留原有的顺序，则需要将后面的元素一个个先前“挪”一格位置，这样操作的话，算法的时间复杂度是较高的。
所以就有了双指针法，分为快慢指针法以及左右指针法，能够实现在一个for循环下完成两个for循环的工作。
而关于本题，有个很重要的条件就是，所给定的数组是有序的，是按升序排序的，这就大大简化了算法的难度。
而关于数组删除元素相关的题目，我们可以避免在中间删除元素，而是可以想办法把要删除的元素换到最后去，最后一起删除。
两遍循环：
我们可以利用一种最朴素的方法，即暴力地使用两遍for循环进行求解，外层的for循环用于查找重复的元素，当寻找到重复的元素后，利用内层的for循环，将数组集体向前移动一位。
//暴力解法
int removeDuplicates(vector<int>& nums) {
int size = nums.size();
for (int i = 0; i < size-1; i++) {
if (nums[i] == nums[i+1]) { // 发现重复的元素
for (int j = i + 1; j < size; j++) { //将数组集体向前移动一位
nums[j - 1] = nums[j];
}
i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
size--; // 记录此时的数组大小
}
}
return size;
}
本题使用暴力解法在LeetCode上是会超时的。
这里面有个细节问题，就是外层for循环的结束条件是i<size-1而不是size，若是size的话会因为之前数组元素集体向前移动，导致最后一次遍历中，必定出现ums[i] == nums[i+1]，这样就会导致多删除一个元素。由于最后一个元素在前一轮循环中，已经比较过了，所以循环到size-1即可。
快慢双指针：
设置快慢双指针，分别指向数组，完成各自任务。
快指针：不停止，勇往直前，寻找重复元素
慢指针：用于记录更新新数组的下标位置
int removeDuplicates2(vector<int>& nums) {
int slow = 0; //初始化慢指针
for (int fast = 0; fast < nums.size()-1; fast++) { //快指针对整个数组进行遍历，寻找重复值
if (nums[fast]!= nums[fast+1]) { //若不为目标值，更新慢指针，并赋值给新数组
nums[slow] = nums[fast];
slow++;
}
}
//最后一位另外作讨论
nums[slow] = nums[nums.size()-1];
slow++;
return slow;
}
这里我用的是将遍历到的数组元素与它后面一位的元素作比较，若是两元素相等，则不更新slow指针，若是和后一位不等，说明是不重复的新元素，更新slow指针。
这么做有一个弊端：数组的最后一位没有后一位元素。所以最后一位要单独拿出来考虑，由于没有后一位元素，数组的最后一位必定是不重复的新元素，可以直接加入到slow新数组中，这里我是将循环结束条件设为fast < nums.size()-1,然后再循环结束后，单独将最后一位添加至slow对应的新数组中。
当然，为了很好地规避这个问题，我们可以使用后一位与前一位作比较的方法，这个时候，数组为空的情况要拿出来单独讨论：
//来自leetcode官方题解
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
进一步优化版：
经过进一步思考发现，只需将快慢指针所对应的值进行比较即可。
//最终优化版
int removeDuplicates4(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
int slow = 0;
for (int fast = 0; fast < n; fast++) {
if (nums[slow] != nums[fast]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
后续也会坚持更新我的LeetCode刷题笔记，欢迎大家关注我，一起学习。
如果这篇文章对你有帮助，或者你喜欢这篇题解，可以给我点个赞哦。
CSDN同步更新，欢迎关注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode学习笔记,HTML+CSS+JS,数据结构领域博主
往期回顾：
LeetCode27.移除元素
