题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
题目
给你一个有序数组
nums，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1
- 输入： nums = [1,1,1,2,2,3]
- 输出： 5, nums = [1,1,2,2,3]
- 解释： 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
示例2
- 输入： nums = [0,0,1,1,1,1,2,3,3]
- 输出： 7, nums = [0,0,1,1,2,3,3]
数据范围
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按升序排列
分析
更新博客主题第一篇~ 分析部分不用 > 包起来了 ヽ(￣▽￣)ﾉ
一道乍看简单，细想麻烦的题目，放在 错题本 这个分类里，主要是由于朴素的暴力做法是能通过的。当然，题解里面的想法更为强大，当然，并不是特别难想，但是细节是较多的，也是本次错得最多的地方。
朴素做法
这是我最初的想法。根据题意，最终相同的数字最多只有 两个 ，那么我们使用一个指针向前移动，当它和它的 下一位 元素值相同时，它的 下下位 元素的数值就必须和它不同了。即，当我们向后看去，发现下一个元素与当前元素相同时，可以直接确定下下位元素的值；并且确定了之后，需要从确定的点开始，将后面的元素都向前移动。
移动之后，还需要进行 pop_back() 的操作。
这就跟从一个有序数组中删除数据一样，我们删除的是一段重复的数据，要将后面的东西向前移动，覆盖掉这一段。
这种思路下，限制条件就很多了：
- Q：当前元素没有下一个元素怎么办
- A：说明它到达了最后一个元素，循环结束
- Q：寻找下一个元素的时候有哪些注意点
- A：使用一个指针向后寻找下一个元素，当它不越界且与当前元素仍然相等的时候，继续向后移动；当这一个循环退出之后，说明几个问题：我们找到了下一个元素或者之后没有符合条件的元素，在这里还需要进行一次判断
不得不说，我最开始、最朴素的想法反而特别的复杂，根据上面的内容能写出如下的代码：
AC代码1
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
vector<int>::iterator p_now;
vector<int>::iterator p_next;
vector<int>::iterator p_tmp;
int res, num_now;
for (p_now = nums.begin(); p_now < nums.end(); )
{
if (p_now == nums.end() - 1)
{
p_now++;
break;
}
if (*p_now == *(p_now + 1))
{
num_now = *p_now;
p_now += 2;
p_next = p_now;
// get next num different from now
while (p_next < nums.end() && *p_next == num_now)
{
p_next++;
}
// next position is valid
if (p_next < nums.end() && p_next != p_now)
{
p_tmp = p_now;
int diff = p_next - p_now;
while (p_next < nums.end())
{
*p_tmp = *p_next;
p_next++;
p_tmp++;
}
while (diff-- > 0)
{
nums.pop_back();
}
}
// next position is invalid
else if (p_next == nums.end())
{
break;
}
}
else
{
p_now++;
}
}
// cout << *p_now << endl;
res = p_now - nums.begin();
while (nums.size() > res)
{
nums.pop_back();
}
return res;
}
};
大几十行的代码，没什么好说的了 -_-||
对于原地修改来说，我的 pop_back() 操作实际上显得多余，表现是很一般的：
双指针
对于上面的做法，向后看 的思想使得我对于循环边界条件的判断比较困难，因为我们总是要考虑当前元素的 下一位 、 下下位 ，很容易就产生越界的问题。
如果 向前看 ，怎么做呢？
双指针的思想是，使用 快慢指针 ，慢指针 slow 指向当前的位置，快指针 fast 指向当前位置 应该填充 的元素；向前看去，当 *slow == *(slow - 2) 时，继续移动 fast 而使 slow 保持不动，直到符合 *slow != *fast ，即改变当前元素的值使得它不再与之前的元素相同。
千言万语不如一张GIF（请点开它）：
注意当 slow 指向了第三个 2 的时候，*slow == *(slow - 2) ，则 slow 不再继续前移，只移动 fast ，且只当 *fast ！= *slow 的时候才会继续移动 slow 。在本例中，将 *slow 更新为 3 之后， fast 和 slow 都要继续移动，然而 fast 已经走完了整个数组，故循环结束了。
由此写出AC代码2.
AC代码2
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
vector<int>::iterator slow;
vector<int>::iterator fast;
slow = nums.begin();
for (fast = nums.begin(); fast < nums.end(); fast++)
{
*slow = *fast;
if (slow < nums.begin() + 2)
{
slow++;
continue;
}
if (*slow == *(slow - 2) && *slow == *fast)
{
// do not add slow
// cout << *slow << " == " << *fast << endl;
// cout << slow - nums.begin() << endl;
continue;
}
slow++;
}
/*
for (vector<int>::iterator tmp = nums.begin(); tmp != slow; tmp++)
{
cout << *tmp << " ";
}
cout << endl;
cout << "Ret: " << slow - nums.begin() << endl;
*/
return slow - nums.begin();
}
};
我将调试代码都留在了此处，这是因为AC代码中有一步细节需要注意：
for (fast = nums.begin(); fast < nums.end(); fast++) { *slow = *fast; // --- snip --- }
fast的每一步移动都要伴随着slow的更新，并不需要关注slow满足什么条件。仅当slow与它的上上位不同的时候才会继续移动，因此不必担心赋值出现什么问题。这一步可是我WA了三次才得到的惨痛教训！
参考资料
[1] 力扣官方题解.删除排序数组中的重复项 II[EB/OL].2021-04-05
[2] 负雪明烛.【负雪明烛】动画题解，帮助理清思路[EB/OL].2021-04-06
