080 移除有序数组中的重复项 II
🔗 相关链接
📜 题目描述
给定一个有序数组 nums，需要 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次，返回删除后数组的新长度。不要使用额外的数组空间，必须在 原地 修改输入数组，并在使用 O(1) 额外空间的条件下完成。
说明
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
可以想象内部操作如下：
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}📊 示例
示例 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]解释：
函数应返回新长度 length = 7，并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。
📝 提示
1 <= nums.length <= 3 * 10^4-10^4 <= nums[i] <= 10^4nums已按升序排列
💡 思路
对比026 移除有序数组中的重复项，该题难度上升在不能开辟额外的数组保存某个值是否达到删除的条件。根据题目，每个数字最多可以出现两次，即需要满足条件 nums[i] == nums[i-1] == nums[i-2] (i >= 2)。
使用 while 循环和快慢指针遍历数组，初始化 slow 和 fast 为 2（数组长度小于 2 的条件不需要比较，可以直接返回）并比较 nums[slow-2] 与 nums[fast]，若不同则直接赋值。
nums[slow-2] 表示已经被确定需要保留的值，即刚开始 slow 和 fast 都为 2 时，0（slow-2）为第一个确定需要保留的元素。若 nums[slow-2] 与 nums[slow-1] 相同，则 nums[slow] 不需要被保留。
提示
LeetCode官方定义
我们定义两个指针 slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度，即 nums[fast] 表示待检查的第一个元素，nums[slow−1] 为上一个应该被保留的元素所移动到的指定位置。
因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 nums[slow−2] 是否和当前待检查元素 nums[fast] 相同。当且仅当 nums[slow−2]=nums[fast] 时，当前待检查元素 nums[fast] 不应该被保留（因为此时必然有 nums[slow−2]=nums[slow−1]=nums[fast]）。最后，slow 即为处理好的数组的长度。
💻 代码实现
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) {
return nums.length;
}
int slow = 2, fast = 2;
while (fast < nums.length) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}